A directed Andrásfai-Erdős-Sós theorem and chromatic profiles of oriented cycles
Yisai Xue · 2025
Read A directed Andrásfai-Erdős-Sós theorem and chromatic profiles of oriented cycles by Yisai Xue (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07760.txt.
Introduction
Yisai Xue, writing alone in 2025, determines chromatic profiles for several classes of directed graphs. A digraph is a network whose links have directions. The chromatic profile of a digraph H measures the smallest minimum out-degree that forces any H-free digraph with that out-degree to be colorable with a given number of colors. Exact values were unknown for the fundamental classes treated here.
The main result is a directed analogue of the Andrásfai-Erdős-Sós theorem, giving the exact profile for transitive tournaments, the fully ordered directed complete graphs. Directed odd cycles all share the profile value one half for two-colorability. The three remaining orientations of the pentagon each give one third. Such exact thresholds are prized in extremal combinatorics because they convert degree conditions into clean structural guarantees.
Catalog record
| CREATOR | Yisai Xue |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-07760
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A directed Andrásfai-Erdős-Sós theorem and chromatic profiles of oriented cycles Yisai Xue Abstract The chromatic profile of a digraph H H , denoted by δ χ + ( H , k ) \delta_{\chi}^{+}(H,k) , is the infimum d d such that any H H -free digraph D D on n n vertices with minimum out-degree δ + ( D ) ≥ d n \delta^{+}(D)\geq dn must be k 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 \delta_{\chi}^{+}(T_{r},r-1)=\frac{3r-7}{3r-4} , where T r T_{r} is the transitive tournament on r r vertices. We then determine the chromatic profile for directed odd cycles, showing that δ χ + ( C → 2 ℓ + 1 , 2 ) = 1 / 2 \delta^{+}_{\chi}(\overrightarrow{C}_{2\ell+1},2)=1/2 for all ℓ ≥ 1 \ell\geq 1 . Finally, we resolve the profile for the three remaining orientations of the pentagon, establishing that δ χ + ( C 5 ′ , 2 ) = δ χ + ( C 5 ′′ , 2 ) = δ χ + ( C 5 ′′′ , 2 ) = 1 / 3 \delta_{\chi}^{+}(C_{5}^{\prime},2)=\delta_{\chi}^{+}(C_{5}^{\prime\prime},2)=\delta_{\chi}^{+}(C_{5}^{\prime\prime\prime},2)=1/3 . 1 Introduction The celebrated Andrásfai-Erdős-Sós theorem [ 4 ] states that for r\geq 3 , any n -vertex K_{r} -free graph G with minimum degree \delta(G)>\frac{3r-7}{3r-4}n is (r-1) -colorable. This bound is sharp (see Fig. 2.2 ). The general problem of determining the minimum degree threshold that guarantees a certain chromatic number in H -free graphs is known as the chromatic profile problem. Formally, the chromatic profile of a graph H is defined as \displaystyle\delta_{\chi}(H,k):=\inf\{d:\delta(G)\geq d|G|\text{ and }H\not\subseteq G\Rightarrow\chi(G)\leq k\}. The case of triangle-free graphs has been extensively studied. It is known from the work of Andrásfai, Erdős and Sós [ 4 ] , Brandt and Thomassé [ 8 ] , Häggkvist [ 13 ] and Jin [ 17 ] that \delta_{\chi}(K_{3},2)=\frac{2}{5},\quad\delta_{\chi}(K_{3},3)=\frac{10}{29}\quad\text{ and }\quad\delta_{\chi}(K_{3},k)=\frac{1}{3}\quad\text{ for every }k\geq 4. Goddard and Lyle [ 12 ] , and independently Nikiforov [ 24 ] extended these results by showing that \delta_{\chi}(K_{r},r)=\frac{19r-47}{19r-28} and \delta_{\chi}(K_{r},r+1)=\frac{2r-5}{2r-3} . For odd cycles, Häggkvist [ 13 ] showed that \delta_{\chi}(C_{2\ell+1},2)=\frac{2}{2\ell+3} for 1\leq\ell\leq 4 . More recently, Yuan and Peng [ 27 ] established that \delta_{\chi}(C_{2\ell+1},2)=\frac{1}{6} for \ell\geq 5 . The problem for an arbitrary graph H was also posed by Erdős and Simonovits [ 10 ] , who described it as “too complicated” in its full generality. For more related results, see [ 1 , 5 , 6 , 14 , 15 , 16 , 19 , 22 , 23 , 21 , 26 ] . The chromatic profile problem connects extremal and coloring theory by asking how a “local” density condition (minimum degree), rather than a “global” one, constrains the chromatic number of an H -free graph. This framework, exemplified by the Andrásfai-Erdős-Sós theorem, studies the stability of chromatic properties in graphs that are dense but not necessarily extremal. The extension to digraphs introduces two primary challenges: the proliferation of forbidden structures due to their various orientations, and the structural asymmetries that demand new proof techniques. All digraphs considered in this paper are finite, may contain anti-parallel arcs (i.e., directed 2-cycles), but have no loops or parallel arcs. The chromatic profile of a digraph H is defined as: \displaystyle\delta^{+}_{\chi}(H,k):=\inf\{d:\delta^{+}(D)\geq d|D|\text{ and }H\not\subseteq D\Rightarrow\chi(D)\leq k\}. (1) Here, \delta^{+}(D) denotes the minimum out-degree of the digraph D . Our first result generalizes the Andrásfai-Erdős-Sós theorem to the directed setting by determining the profile of the transitive tournament T_{r} on r vertices. Theorem 1.1 . \delta^{+}_{\chi}(T_{r},r-1)=\frac{3r-7}{3r-4} . Notably, by replacing each edge in an undirected graph with a pair of anti-parallel arcs, one can recover the Andrásfai-Erdős-Sós theorem as a direct corollary of Theorem 1.1 . Moreover, as an application, we obtain the following stability theorem. Theorem 1.2 . Let r\geq 3,t\geq 1 be integers and \varepsilon>0 . Let D be a T_{r}[t] -free digraph on n vertices with minimum out-degree \delta^{+}(D)\geq(\frac{3r-7}{3r-4}+\varepsilon)n . If n is sufficiently large, then one can delete o(n^{2}) arcs to make D an (r-1) -partite digraph. Our second result determines the 2-coloring profile for directed odd cycles. Theorem 1.3 . For every \ell\geq 1 , we have \delta^{+}_{\chi}(\overrightarrow{C}_{2\ell+1},2)=\frac{1}{2} . \overrightarrow{C}_{5} C^{\prime}_{5} C^{\prime\prime}_{5} C^{\prime\prime\prime}_{5} Figure 1.1 : Orientations of C_{5} Finally, we investigate the chromatic profile for orientations of the pentagon C_{5} . There are four non-isomorphic orientations of the pentagon, depicted in Fig. 1.1 . While Theorem 1.3 addresses the profile for \overrightarrow{C}_{5} , our final result resolves the 2-coloring profiles for the three remaining cases. Theorem 1.4 . \delta^{+}_{\chi}(C^{\prime}_{5},2)=\delta^{+}_{\chi}(C^{\prime\prime}_{5},2)=\delta^{+}_{\chi}(C^{\prime\prime\prime}_{5},2)=\frac{1}{3} . The remainder of this paper is organized as follows. In Section 2 , we prove our main result, a directed analogue of the Andrásfai-Erdős-Sós theorem, which determines the chromatic profile for transitive tournaments. Section 3 is devoted to directed odd cycles, where we establish their 2-coloring profile. In Section 4 , we complete the picture for pentagon orientations by resolving the 2-coloring profiles for the remaining three cases. We then present an application of our main theorem in Section 5 , proving a stability theorem. Finally, in Section 6 , we conclude with a discussion of related concepts and pose several open questions for future research. Notations. We write u\to v or (u,v) to denote an arc from u to v , and say that u dominates v . For a vertex v in a digraph D , its in-neighbourhood N_{D}^{-}(v) is the set \{u\in V(D):u\to v\} , and its out-neighbourhood N_{D}^{+}(v) is the set \{u\in V(D):v\to u\} . The in-degree d_{D}^{-}(v) and out-degree d_{D}^{+}(v) are the sizes of these sets, respectively. A vertex of in-degree zero is called a source ; one of out-degree zero a sink . We omit the subscript D when the context is clear. For v\in V(D) and S\subseteq V(D) , let d^{+}(v,S) denote the number of arcs from v to S . Similarly, let d^{+}(S,v) denote the number of arcs from S to v . For two graphs G and H , the join G\vee H is formed by taking disjoint copies of G and H , and adding all edges between V(G) and V(H) . The s -blowup of a graph G , denoted by G[s] , is obtained by replacing each vertex v\in V(G) with an independent set I_{v} of size s , and adding all edges between I_{u} and I_{v} whenever uv\in E(G) . For S\subseteq V(D) , D[S] denotes the subgraph induced by S . The underlying graph G(D) of a digraph D is the simple graph on V(D) where \{u,v\} is an edge if and only if (u,v) or (v,u) is an arc in D . For a graph G , we let \overleftrightarrow{G} denote its double orientation, where each edge uv is replaced by the pair of arcs (u,v) and (v,u) . The odd girth g_{\text{odd}}(D) of a digraph D is the length of a shortest odd cycle in its underlying graph G(D) . The independence number \alpha(D) is the size of