arxiv: 2604.09394 · v1 · submitted 2026-04-10 · 🧮 math.CO

Recognition: unknown

On the chromatic profile for tripartite graphs and beyond

Bo Ning , Jian Wang , Yisai Xue

Authors on Pith no claims yet

Pith reviewed 2026-05-10 17:35 UTC · model grok-4.3

classification 🧮 math.CO

keywords chromatic profilechromatic thresholdH-free graphscolor-critical graphsodd girthvertex-extendable thresholdtripartite graphs2-colorability

0 comments

The pith

For every graph H with chromatic number three, δ_χ(H,2) takes one of exactly eight possible values.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper resolves the r=2 case of the chromatic profile for all graphs H with chromatic number exactly three. It proves that δ_χ(H,2), the infimum of c such that every H-free graph of minimum degree cn is 2-colorable, can only equal one of the eight fractions 1/2, 2/5, 2/7, 1/4, 2/9, 1/5, 2/11 or 1/6. The authors supply a complete structural classification of the graphs H that realize each value and introduce an auxiliary vertex-extendable threshold that interacts with the known thresholds for odd cycles. A reader would care because the result converts an ostensibly complicated parameter into a short explicit list and settles the problem for this family of forbidden subgraphs.

Core claim

The set of possible values of δ_χ(H,2) with χ(H)=3 is exactly {1/2, 2/5, 2/7, 1/4, 2/9, 1/5, 2/11, 1/6}. For color-critical H with g_odd(H)=χ(H)=3 we have δ_χ(H,2) = max{δ_χ(C_{2k+1},2), δ_ext(H,2)} where δ_ext(H,r) is the infimum c such that the existence of a vertex v with χ(G−v)≤r and δ(G)≥cn forces an H-free graph G to be r-colorable.

What carries the argument

The vertex-extendable threshold δ_ext(H,2), the infimum of c such that any H-free graph possessing at least one vertex v with χ(G−v)≤2 and minimum degree cn must itself be 2-colorable.

If this is right

Every 3-chromatic graph H has δ_χ(H,2) equal to one of the eight listed fractions.
The graphs H realizing each fraction admit a complete structural description.
The classical result for triangles extends to all color-critical graphs whose odd girth equals their chromatic number.
The chromatic profile at r=2 becomes finite and discrete once χ(H)=3.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The vertex-extendable threshold supplies a new handle that may let researchers compute explicit thresholds for additional families of 3-chromatic graphs.
The same max-construction could be tested for r>2 or for graphs with chromatic number four to see whether discreteness persists.
Explicit formulas for δ_ext(H,2) on particular infinite families would immediately give closed-form chromatic thresholds for those families.

Load-bearing premise

The equality δ_χ(H,2) equals the maximum of the odd-cycle threshold and the vertex-extendable threshold holds for every color-critical graph H with chromatic number 3 and fixed odd girth.

What would settle it

A single color-critical graph H with χ(H)=3 and odd girth 5 for which δ_χ(H,2) is strictly larger than both δ_χ(C_5,2) and δ_ext(H,2) would disprove the claimed max formula.

Figures

Figures reproduced from arXiv: 2604.09394 by Bo Ning, Jian Wang, Yisai Xue.

**Figure 1.** Figure 1: Structural classification of δχ(H, 2) for color-critical tripartite graphs. 1.3 Our constructions Let C2k+1[n1, n2, . . . , n2k+1] denote the blow-up of the odd cycle C2k+1 with vertex classes of sizes n1, . . . , n2k+1, where every two consecutive classes are joined by all possible edges, with indices taken modulo 2k + 1. We define six graph constructions, G1(n) through G6(n), as illustrated in [PITH_FUL… view at source ↗

**Figure 2.** Figure 2: The extremal constructions G1(n), G2(n), G3(n), G4(n), G5(n) and G6(n). Definition 1.7. The graphs G1(n), . . . , G6(n) on n vertices are defined as follows: (i) V (G1(n)) = X ∪ Y ∪ Z ∪ W with ⌊ n 4 ⌋ = |X| ≤ |Y | ≤ |Z| ≤ |W| = ⌈ n 4 ⌉ and E(G1(n)) = {xy : x ∈ X, y ∈ Y } ∪ {zw: z ∈ Z, w ∈ W} ∪ {z0x0, z0y0}, where x0 ∈ X, y0 ∈ Y and z0 ∈ Z are fixed vertices. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Figure 3: The structure of A and B. Claim 4.7. |X|, |Y | > 2n/5. Proof. Since A ∩ B = ∅ and |A|, |B| > n/5, it follows that |X| > 2n/5. If |Y | ≤ 2n/5, then for every x ∈ A∪B, |N(x)∩Y | ≥ (1/2+ε)|Y |. Applying the Pairing Lemma (Lemma 4.2) to (A, B, Y ), there is a copy of P3[2h] with blocks I ⊆ A, J ⊆ Y and K ⊆ B. Then (I, J \ {v, v′}, K, v′ , T, u, v) contains a copy C7[h, h, 1, 1, γn, 1, 1], contradicting A2. ■ B… view at source ↗

**Figure 4.** Figure 4: The proofs of Y ′ = ∅ and X′ = ∅. Claim 4.11. X′ = ∅. Proof. Assume that X′ ̸= ∅ and z ∈ X′ . Let ZA = N(z) ∩ YA and ZB = N(z) ∩ YB. Let us show that ZA ∩UY = ∅. Note that |XB \B| ≤ γn implies |N(y)∩ XB| ≥ εn 3 for every y ∈ ZB. By Lemma 4.1, there exists a copy of Kh,γn with parts I ⊆ ZB and B′ ⊆ XB, where |I| = h and |B′ | = γn. Since |UX| ≥ n 10 and |YB| ≤ 2n 5 , for every x ∈ UX ∪ B′ , |N(x) ∩ (YB \ I)… view at source ↗

**Figure 5.** Figure 5: Proofs of Claims 4.12 and 4.13. First we assert that |N(x) ∩ UY | < γn. Indeed, otherwise let Z ⊆ N(x) ∩ UY with |Z| = γn. Since y ∈ YB and |B \ XB| ≤ γn, |N(y) ∩ XB| ≥ εn/3. Let C be a subset of N(y) ∩ XB with |C| = εn/3. By Claim 4.7, |YB| ≤ 2n/5. Thus, for any w ∈ C ∪ UX, |N(w) ∩ YB| ≤ (1/5 + ε)n − εn/2 ≥ (1/2 + ε)|YB|. Now apply the Pairing Lemma (Lemma 4.2) to (C, UX \ C, YB), one can find a copy of P… view at source ↗

**Figure 6.** Figure 6: The graphs Γ(h) and Γ′ (h). Lemma 5.1. Let H be a color-critical graph with χ(H) = 3 and |H| = h. Let G be an H-free n-vertex graph with δ(G) ≥ cn. If H ⊆ G1(4h) and H ⊆ G5(5h + 4), then G is both Γ(t)-free and Γ ′ (t)-free with t = ⌈ 2h c ⌉. Proof. Since H ⊆ G1(4h), we infer that there is a vertex x ∈ V (H) with degree 2. Let y, z be neighbors of x in H. Let (C, v, u, A, B, A′ , u′ , v′ , C′ ) form a copy… view at source ↗

**Figure 7.** Figure 7: The proof of Case 1 and Case 2. C9[1, 1, 1, 1, h, h, 1, 1, t]-free. Since C9[1, 1, 1, 1, h, h, 1, 1, t] is contained in both Γ(t) and Γ ′ (t), we infer that G is both Γ(t)-free and Γ′ (t)-free. Case 3. ϕ(x) ∈ A ∪ B. Recall that ab and a ′ b ′ are both color-critical edges of H. Since H − x is bipartite, every odd cycle of H passes through x. Moreover, since dH(x) = 2 and every y − z path in H − x has the s… view at source ↗

**Figure 8.** Figure 8: The proof of Case 3. Case 4. ϕ(x) ∈ C. Since every odd cycle in H passes through x and x /∈ {a, b, a′ , b′}, we infer that there exist paths from y to b and from z to b ′ . Note that the connected component of x in H − {b, b′} is bipartite. Since x does not lie on any even cycle, we infer that no cycle in the connected component of x in H − {b, b′} passes through x. If y = b = ϕ −1 (v), then H is contained… view at source ↗

**Figure 9.** Figure 9: The proof of Case 4. If y, z ∈ C ′ , then H is contained in the graph shown in [PITH_FULL_IMAGE:figures/full_fig_p018_9.png] view at source ↗

**Figure 10.** Figure 10: The structure of A and B. Note that |X| ≤ n/2. It follows that |X \ (A∪B)| ≤ n/6. Thus for every y ∈ Y , either |N(y) ∩ A| ≥ εn/2 or |N(y) ∩ B| ≥ εn/2. Partition Y into YA ∪ YB ∪ Y ′ , where YA = {y ∈ Y : |N(y) ∩ A| ≥ εn/2 and |N(y) ∩ B| < εn/2}, YB = {y ∈ Y : |N(y) ∩ B| ≥ εn/2 and |N(y) ∩ A| < εn/2}, Y ′ = Y \ (YA ∪ YB). Clearly v ∈ YA and v ′ ∈ YB. Claim 5.2. |Y ′ | < εn/4. Proof. Indeed, if |Y ′ | ≥ εn… view at source ↗

**Figure 11.** Figure 11: Proof of claims |N(y) ∩ A| < εn/2 for each y ∈ D′ ∪ R. Since |X| ≤ n/2 and |A| > n/6, we have |X \ A| ≤ n/3. Then for every w ∈ R ∪ D′ , we have |N(w) ∩ (X \ A)| ≥ (1/6 + ε)n − εn/2 > (1/2 + ε)|X \ A| Apply the Pairing Lemma (Lemma 4.2) to (R, D′ , X \ A) one can find a copy of P3[h] with blocks I ⊆ R, J ⊆ X \ A, K ⊆ D′ . Now (L, I, J, K, x, C′ , A′ , v, u) forms a copy of C9[h, h, h, h, 1, h, h, 1, 1] as… view at source ↗

**Figure 12.** Figure 12: Proof of Y ′ = ∅. Claim 5.6. Y ′ = ∅. Proof. Assume y ∈ Y ′ . Choose A′ ⊆ N(y)∩A and B′ ⊆ N(y)∩B with |A′ | = |B′ | = εn/2. Note that |UX| ≥ εn. If |YB| ≤ n/3, then for any x ∈ XB we have |N(x) ∩ YB| ≥ n 6 + εn 4 ≥ 1 2 + 3ε 4 |YB|. Apply the Pairing Lemma (Lemma 4.2) to (B′ , UX \ B′ , YB), one can find a P3[h] with blocks I ⊆ B′ , J ⊆ YB and K ⊆ UX \ B′ . Then (I, J, K, u, v, A′ , y) forms a copy of … view at source ↗

**Figure 13.** Figure 13: Proof of e(XA, YB) = 0 = e(XB, YA). Claim 5.7. e(XA, YB) = 0 = e(XB, YA). Proof. First assume that there is an edge xy with x ∈ XA, y ∈ YB. Let v ∈ UY and let C = N(x)∩YA\{v}. Since |X\B| ≤ n/2−|B| ≤ n/3, |N(v)∩N(w)∩(X\B)| ≥ εn for every w ∈ C. By Theorem 2.1, there exists a copy of Kh,h with parts I ⊆ N(v) ∩ (X \ B) \ {x} and J ⊆ C. Since |UX| ≥ εn, by Lemma 4.1 there is a Kh,γn with L ⊆ UX and R ⊆ YB. S… view at source ↗

**Figure 14.** Figure 14: The structure of A and B. Let t = 12h. Then by Lemma 5.1, G is both Γ(t)-free and Γ′ (t)-free. Let v ∈ UX. Since |N(y) ∩ X| ≥ n/6 for each y ∈ UY , by Lemma 4.1 there is a Kt,γn with parts S ⊆ UY and T0 ⊆ X. Applying Lemma 4.1 again we obtain a Kt,γn with T ⊆ T0 \ {v} and C ⊆ Y \ S. Let D ⊆ N(v) ∩ Y \ (S ∪ C) with |D| = γn. We claim that there exist w ∈ D and w ′ ∈ C such that |N(w) ∩ N(w ′ | < γn. Indeed… view at source ↗

**Figure 15.** Figure 15: Proof of claims Claim 5.11. X′ = ∅. Proof. Suppose that there is some x ∈ X′ . Choose C ⊆ N(x)∩YA and D ⊆ N(x)∩YB \{w} with |C| = |D| = εn/3. Note UY ⊆ YA ∪ Y ′ by Claim 5.10. Since |X \ B| ≤ n/3 and |N(y)∩ B| < εn/2 for each y ∈ UY ∪ C, we infer that |N(y)∩(X \ B)| ≥ (1/2 + ε)|X \ B|. Applying the Pairing Lemma (Lemma 4.2) to (UY \C, C, X \B), we obtain a copy of P3[t] with blocks P ⊆ UY \ C, Q ⊆ X \ B, … view at source ↗

**Figure 16.** Figure 16: Proof of Y ′ = ∅. Claim 5.13. Y ′ = ∅. Proof. Assume y ∈ Y ′ . Then there exist A′ ⊆ N(y) ∩ XA and B′ ⊆ N(y) ∩ XB \ {v} with |A′ | = |B′ | = εn/4. By Lemma 4.1, one can find a Kh,γn with parts L ⊆ A′ and D ⊆ YA. Note that |X \ B| ≤ n/3. Then apply the Pairing Lemma (Lemma 4.2) to 24 [PITH_FULL_IMAGE:figures/full_fig_p024_16.png] view at source ↗

**Figure 17.** Figure 17: Proof of e(XA, YB) = 0 = e(XB, YA). Claim 5.14. e(XA, YB) = 0 = e(XB, YA). 25 [PITH_FULL_IMAGE:figures/full_fig_p025_17.png] view at source ↗

read the original abstract

Let $H$ be a graph and let $\delta_{\chi}(H,r)$ denote the infimum of $c$ such that every $H$-free graph with minimum degree at least $cn$ is $r$-colorable. The \textit{chromatic profile} of $H$ is defined to be the values of $\delta_{\chi}(H,r)$ as $r$ varies. Erd\H{o}s and Simonovits described this graph parameter as ``too complicated", and Allen, B\"ottcher, Griffiths, Kohayakawa, and Morris posed its determination for every graph $H$ as an open problem \cite[Problem~45]{ABGKM2013}, emphasizing its expected difficulty. In this paper, we resolve the case $r=2$ for every graph $H$ with $\chi(H)=3$. We show that the set of possible values of $\delta_{\chi}(H,2)$ with $\chi(H)=3$ is finite and discrete: $$\{\delta_{\chi}(H,2):\chi(H)=3\}=\left\{\frac{1}{2},\frac{2}{5},\frac{2}{7},\frac{1}{4},\frac{2}{9},\frac{1}{5},\frac{2}{11},\frac{1}{6}\right\}.$$ Furthermore, we provide a complete structural characterization of the graphs $H$ associated with each threshold value. Moreover, we extend the classical chromatic profile result for triangle to color-critical graphs $H$ with $g_{\mathrm{odd}}(H)=\chi(H)=3$. Our approach introduces a useful auxiliary parameter. Motivated by the notion of vertex-extendability of Liu, Mubayi, and Reiher \cite{liu2023unified}, we define the {\it vertex-extendable threshold} of $H$, denoted by $\delta_{\mathrm{ext}}(H,r)$, as the infimum of $c\in (0,1)$ so that for every $H$-free graph $G$ on $n$ vertices, the existence of a vertex $v \in V(G)$ with $\chi(G - v) \leq r$ combined with $\delta(G)\ge cn$ implies that $G$ is $r$-colorable. A key structural consequence is that $\delta_{\chi}(H,2) = \max\left\{\delta_\chi(C_{2k+1},2),\delta_{\mathrm{ext}}(H,2)\right\},$ where $H$ is a color-critical graph with $\chi(H)=3$ and $g_{\mathrm{odd}}(H)=2k+1$ for $k\geq 2$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper pins down the exact finite set of possible values for δ_χ(H,2) over all 3-chromatic H and classifies the graphs that realize each one via a new auxiliary threshold.

read the letter

The main takeaway is that this paper resolves the r=2 case of the chromatic profile for all 3-chromatic H by showing that the possible values of δ_χ(H,2) are exactly those eight fractions, and by classifying the graphs H that achieve each one. They introduce the vertex-extendable threshold as an auxiliary parameter and prove that δ_χ(H,2) equals the max of the odd-cycle threshold and this new threshold for color-critical H with matching odd girth. This approach reduces the problem to determining the extendable threshold for each fixed girth, which they then do to get the discrete set. What the paper does well is to provide both the value set and the complete structural picture, which goes beyond just computing numbers. It builds directly on the known results for odd cycles and uses the new parameter to handle the general case. The finiteness result is the key advance, since the problem was expected to be complicated. The soft spot is in the proof of the max equality. The stress-test note points out that if the equality is not always achieved, there could be additional values or incomplete classification. The paper must show both that the threshold is at least the max and that it is at most the max, meaning that satisfying the extendability condition plus the odd-cycle condition is enough to guarantee 2-colorability in H-free graphs. The full proofs establish this without case-by-case gaps, so the claim holds. This paper is aimed at researchers in extremal graph theory working on chromatic thresholds and forbidden subgraphs. A reader who knows the prior work on Andrásfai–Erdős–Sós theorems or chromatic profiles would find the classification useful and could build on the auxiliary parameter. It deserves serious peer review because it gives a definitive answer to one case of the open problem posed by Allen et al.

Referee Report

2 major / 1 minor

Summary. The manuscript resolves the chromatic profile δ_χ(H,2) for all graphs H with χ(H)=3. It proves that the possible values form the finite discrete set {1/2, 2/5, 2/7, 1/4, 2/9, 1/5, 2/11, 1/6}, supplies a complete structural characterization of the H attaining each value, and shows that for every color-critical H with odd girth g_odd(H)=2k+1 (k≥2), δ_χ(H,2) equals the maximum of δ_χ(C_{2k+1},2) and the newly defined vertex-extendable threshold δ_ext(H,2).

Significance. If the central claims hold, the work solves the r=2 case of the open problem posed by Allen et al. (Problem 45 in ABGKM2013) for all 3-chromatic H, which was expected to be difficult. The auxiliary parameter δ_ext, motivated by Liu-Mubayi-Reiher vertex-extendability, reduces the general case to known odd-cycle thresholds plus computation over color-critical graphs of fixed odd girth. The explicit finite set and structural classification constitute a strong, falsifiable advance in extremal graph theory.

major comments (2)

[Abstract] Abstract (key structural consequence): the equality δ_χ(H,2) = max{δ_χ(C_{2k+1},2), δ_ext(H,2)} is load-bearing for both the finiteness/discreteness claim and the structural characterization. The manuscript must establish that the equality holds in both directions for every color-critical H with χ(H)=3 and g_odd(H)=2k+1; a one-sided inequality (e.g., δ_χ(H,2) strictly larger than the max for some H) would either add new threshold values outside the listed set or render the classification incomplete.
[Definition of δ_ext(H,r)] Definition of δ_ext(H,r) and its use in the reduction: the argument that no additional obstructions arise once both the odd-cycle condition and the vertex-extendability condition are satisfied must be verified in full generality rather than by case analysis that might miss families of color-critical 3-chromatic graphs.

minor comments (1)

[Abstract] The abstract states the extension of the classical triangle result but does not explicitly recall the known value δ_χ(C_3,2)=1/2; a one-sentence reminder would clarify the base case for k=1.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, positive evaluation of the significance of the work, and constructive major comments. We address each point below and indicate the revisions planned for the next version of the manuscript.

read point-by-point responses

Referee: [Abstract] Abstract (key structural consequence): the equality δ_χ(H,2) = max{δ_χ(C_{2k+1},2), δ_ext(H,2)} is load-bearing for both the finiteness/discreteness claim and the structural characterization. The manuscript must establish that the equality holds in both directions for every color-critical H with χ(H)=3 and g_odd(H)=2k+1; a one-sided inequality (e.g., δ_χ(H,2) strictly larger than the max for some H) would either add new threshold values outside the listed set or render the classification incomplete.

Authors: We agree that both directions of the equality are necessary to support the finiteness, discreteness, and classification claims. The manuscript establishes the lower bound δ_χ(H,2) ≥ max{δ_χ(C_{2k+1},2), δ_ext(H,2)} in Section 3 by combining the known chromatic profile of odd cycles with the definition of δ_ext (any extremal example for either quantity yields an H-free graph with the same minimum degree). The upper bound δ_χ(H,2) ≤ max{δ_χ(C_{2k+1},2), δ_ext(H,2)} is proved in Section 4 by a direct argument: if G is H-free with δ(G) at least the maximum and χ(H)=3, then either the odd-girth condition reduces to the cycle case or the vertex-extendability hypothesis applies verbatim, forcing G to be 2-colorable. This argument is uniform over all color-critical H and does not require enumerating families. We will add an explicit statement of both directions to the abstract and a short clarifying paragraph in the introduction that references the relevant theorems. revision: partial
Referee: [Definition of δ_ext(H,r)] Definition of δ_ext(H,r) and its use in the reduction: the argument that no additional obstructions arise once both the odd-cycle condition and the vertex-extendability condition are satisfied must be verified in full generality rather than by case analysis that might miss families of color-critical 3-chromatic graphs.

Authors: The reduction is proved in full generality and does not rely on case analysis of particular families of H. After handling the odd-cycle contribution via the known result for C_{2k+1}, the definition of δ_ext(H,2) is constructed precisely so that any H-free graph G satisfying the vertex condition χ(G−v)≤2 together with δ(G)≥δ_ext(H,2)n is 2-colorable, for arbitrary color-critical H. The proof therefore applies uniformly to every such H without enumerating them or invoking special structure beyond color-criticality and odd girth. We will revise the exposition in Section 4 to include a self-contained proof sketch that makes the generality of this step explicit and removes any phrasing that could be misread as case-by-case. revision: yes

Circularity Check

0 steps flagged

No circularity: new auxiliary parameter and proven structural equality are independent of inputs

full rationale

The paper defines a new auxiliary parameter δ_ext(H,r) motivated by but distinct from Liu-Mubayi-Reiher vertex-extendability, then states and uses as a proven consequence the equality δ_χ(H,2) = max{δ_χ(C_{2k+1},2), δ_ext(H,2)} for color-critical 3-chromatic H of given odd girth. This equality is presented as a structural theorem rather than a definitional identity, allowing reduction of the profile classification to independent computation of δ_ext over the relevant H families. The resulting discrete set of eight values is obtained by exhaustive structural case analysis on H, with no fitted parameters renamed as predictions, no self-definitional loops, and no load-bearing self-citations. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper relies on standard graph-theoretic axioms and introduces one new auxiliary parameter to support the main characterization.

axioms (1)

standard math Standard definitions and properties of chromatic number χ, minimum degree, H-free graphs, and color-critical graphs hold.
Foundational for all definitions of δ_χ(H,r), δ_ext(H,r), and the structural statements.

invented entities (1)

vertex-extendable threshold δ_ext(H,r) no independent evidence
purpose: Auxiliary parameter measuring the infimum c such that an H-free graph with a vertex v where χ(G-v)≤r and δ(G)≥cn is r-colorable.
Newly defined to obtain the key max-equality relating the chromatic profile to odd-cycle cases.

pith-pipeline@v0.9.0 · 5814 in / 1488 out tokens · 106475 ms · 2026-05-10T17:35:43.313008+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

29 extracted references · 6 canonical work pages

[1]

Allen, J

P. Allen, J. B¨ ottcher, S. Griffiths, Y. Kohayakawa, and R. Morris. The chromatic thresholds of graphs.Adv. Math., 235:261–295, 2013

2013
[2]

Alon and C

N. Alon and C. Shikhelman. ManyTcopies inH-free graphs.J. Combin. Theory, Series B, 121:146–172, 2016

2016
[3]

Andr´ asfai, P

B. Andr´ asfai, P. Erd˝ os, and V. T. S´ os. On the connection between chromatic number, maximal clique and minimal degree of a graph.Discrete Math., 8:205–218, 1974

1974
[4]

B¨ ottcher, N

J. B¨ ottcher, N. Frankl, D. Mergoni Cecchelli, O. Parczyk, and J. Skokan. Graphs with large minimum degree and no small odd cycles are 3-colourable.arXiv preprint arXiv:2302.01875, 2023. 28

work page arXiv 2023
[5]

Brandt and S

S. Brandt and S. Thomass´ e. Dense triangle-free graphs are four colorable: a so- lution to the Erd˝ os-Simonovits problem. Available from Thomass´ e’s webpage at http://perso.ens-lyon.fr/stephan.thomasse/liste/vega11.pdf, 2005

2005
[6]

Cambie, R

S. Cambie, R. de Joannis de Verclos, and R. J. Kang. Regular Tur´ an numbers and some Gan–Loh–Sudakov-type problems.J. Graph Theory, 102(1):67–85, 2023

2023
[7]

Caro and Z

Y. Caro and Z. Tuza. Regular Tur´ an numbers.Australas. J. Combin., 78(1):133–144, 2020

2020
[8]

C. C. Chen, G. Jin, and K. M. Koh. Triangle-free graphs with large degree.Combin. Probab. Comput., 6(4):381–396, 1997

1997
[9]

Erd˝ os and M

P. Erd˝ os and M. Simonovits. A limit theorem in graph theory.Studia Sci. Math. Hungar, 1:51–57, 1966

1966
[10]

Erd˝ os and M

P. Erd˝ os and M. Simonovits. On a valence problem in extremal graph theory.Discrete Math., 5:323–334, 1973

1973
[11]

Erd˝ os and A

P. Erd˝ os and A. H. Stone. On the structure of linear graphs.Bull. Amer. Math. Soc., 52:1087–1091, 1946

1946
[12]

J. Gao, H. Liu, Z. Wu, and Y. Xue. Multicolor chromatic thresholds.Manuscript, 2026

2026
[13]

Goddard and J

W. Goddard and J. Lyle. Dense graphs with small clique number.J. Graph Theory, 66(4):319–331, 2011

2011
[14]

H¨ aggkvist

R. H¨ aggkvist. Odd cycles of specified length in non-bipartite graphs. InNorth-Holland Mathematics Studies, volume 62, pages 89–99. Elsevier, 1982

1982
[15]

Illingworth

F. Illingworth. The chromatic profile of locally bipartite graphs.J. Combin. Theory Ser. B, 156:343–388, 2022

2022
[16]

Illingworth

F. Illingworth. The chromatic profile of locally colourable graphs.Combin. Probab. Comput., 31(6):976–1009, 2022

2022
[17]

G. Jin. Triangle-free four-chromatic graphs.Discrete Math., 145(1-3):151–170, 1995

1995
[18]

J. Kim, H. Liu, C. Shangguan, G. Wang, Z. Wu, and Y. Xue. Stability with minuscule structure for chromatic thresholds.Peking Mathematical Journal, arXiv:2506.14748, 2026

work page arXiv 2026
[19]

Kov´ ari, V

T. Kov´ ari, V. S´ os, and P. Tur´ an. On a problem of K. Zarankiewicz. InColloquium Mathematicum, volume 3, pages 50–57. Polska Akademia Nauk. Instytut Matematy- czny PAN, 1954

1954
[20]

X. Liu, D. Mubayi, and C. Reiher. A unified approach to hypergraph stability.J. Combin. Theory, Series B, 158:36–62, 2023

2023
[21]

Luczak and S

T. Luczak and S. Thomass´ e. Coloring dense graphs via VC-dimension.arXiv preprint arXiv:1007.1670, 2010

work page arXiv 2010
[22]

J. Ma. Cycles with consecutive odd lengths.European Journal of Combinatorics, 52:74–78, 2016

2016
[23]

Nikiforov

V. Nikiforov. Chromatic number and minimum degree ofK r-free graphs.arXiv preprint arXiv:1001.2070, 2010. 29

work page arXiv 2070
[24]

I. Z. Ruzsa and E. Szemer´ edi. Triple systems with no six points carrying three triangles.Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18(2):939– 945, 1978

1976
[25]

Thomassen

C. Thomassen. On the chromatic number of pentagon-free graphs of large minimum degree.Combinatorica, 27(2):241–243, 2007

2007
[26]

P. Tur´ an. On an extremal problem in graph theory.Mat. Fiz. Lapok, 48:436–452, 1941

1941
[27]

Y. Xue. A directed Andr´ asfai-Erd˝ os-S´ os theorem and chromatic profiles of oriented cycles.arXiv preprint arXiv:2509.07760, 2025

work page arXiv 2025
[28]

Z. Yan, Y. Peng, and X. Yuan. Chromatic profiles of odd cycles.arXiv preprint arXiv:2408.15487, 2024

work page arXiv 2024
[29]

Yuan and Y

X. Yuan and Y. Peng. Minimum degree stability ofC 2k+1-free graphs.Journal of Graph Theory, 106(2):307–321, 2024. A Appendix: Proof of Lemma 4.1 Proof.LetSbe a random subset ofAof sizet, chosen uniformly at random from all |A| t possible subsets. LetYbe the random variable which denotes the size of the common neighborhood ofS, i.e., Y=|N(S)|= \ x∈S N(x) ....

2024