A directed Andrásfai-Erdős-Sós theorem and chromatic profiles of oriented cycles

2025/09/09 by Yisai Xue, Xue, Yisai · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2509.07760

openalex publication_date 2025/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The chromatic profile of a digraph H, denoted by δ_χ⁺(H,k), is the infimum d such that any H-free digraph D on n vertices with minimum out-degree δ⁺(D) ≥ dn must be k-colorable. We determine the exact chromatic profile for several fundamental classes of digraphs. Our main result is a directed analogue of the Andrásfai-Erdős-Sós theorem, stating that δ_χ⁺(T_r, r-1)=(3 r-7)/(3 r-4), where T_r is the transitive tournament on r vertices. We then determine the chromatic profile for directed odd cycles, showing that δ⁺_χ(\overrightarrowC_2ℓ+1,2)=1/2 for all ℓ≥ 1. Finally, we resolve the profile for the three remaining orientations of the pentagon, establishing that δ_χ⁺(C₅',2)=δ_χ⁺(C₅'',2)=δ_χ⁺(C₅''',2)=1/3.

Citations

• Stability with minuscule structure for chromatic thresholds
• A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
• Orientations of cycles in digraphs of high chromatic number and high minimum out-degree
• Interpolating chromatic and homomorphism thresholds
• Positive codegree Andrásfai--Erdős--Sós theorem for the generalized triangle
• Andrásfai--Erdős--Sós theorem for the generalized triangle
• Chromatic profiles of odd cycles
• Graphs with large minimum degree and no small odd cycles are 3-colourable
• The regularity method for graphs and digraphs
• The chromatic thresholds of graphs
• Chromatic number and mimimum degree of K_r-free graphs

Cited by

• Edge density and minimum degree thresholds for H-free graphs with unbounded chromatic number

Related

• Extension of Gyarfas-Sumner conjecture to digraphs
• Orientations of cycles in digraphs of high chromatic number and high minimum out-degree
• Cycles with two blocks in k-chromatic digraphs
• Subdivisions of Oriented Cycles in Digraphs with Hamiltonian directed path
• χ-bounded families of oriented graphs