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

CREATORYisai Xue
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text