pith. sign in

arxiv: 2604.09394 · v2 · pith:QXN5Y2WZnew · submitted 2026-04-10 · 🧮 math.CO

On the chromatic profile for tripartite graphs and beyond

Bo Ning , Jian Wang , Yisai Xue This is my paper

Pith reviewed 2026-05-21 09:39 UTC · model grok-4.3

classification 🧮 math.CO
keywords chromatic profileH-free graphsminimum degreebipartiteodd girthcolor-criticalvertex-extendable threshold
0
0 comments X

The pith

For every graph H with chromatic number 3 the chromatic threshold δ_χ(H,2) equals one of eight specific rational numbers.

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

The paper resolves the chromatic profile for r=2 when the forbidden graph H requires three colors. It shows that the possible values of the infimum density c forcing every H-free graph of minimum degree cn to be bipartite form a finite discrete set consisting of the fractions 1/2, 2/5, 2/7, 1/4, 2/9, 1/5, 2/11 and 1/6. The authors achieve this by defining a vertex-extendable threshold and proving that the overall threshold is the larger of the threshold for the shortest odd cycle in H and this new parameter. A complete classification of which H realize each value is also given, extending earlier results known only for triangles.

Core claim

When H is color-critical with χ(H)=3 and odd girth 2k+1, δ_χ(H,2) equals the maximum of δ_χ of the cycle C_{2k+1} and the vertex-extendable threshold δ_ext(H,2). This maximum always equals one of the eight listed values, and the paper characterizes the graphs H that produce each value.

What carries the argument

The vertex-extendable threshold δ_ext(H,2), which is the infimum c such that the existence of a vertex v with G-v being 2-colorable together with minimum degree at least cn forces an H-free graph G to be 2-colorable.

If this is right

  • The possible values for δ_χ(H,2) when χ(H)=3 form a finite set.
  • Each value in the set has a complete structural characterization of the realizing graphs H.
  • The formula reduces the problem to computing thresholds for odd cycles and the extendability parameter.
  • Classical results for triangles extend to all color-critical 3-chromatic graphs with fixed odd girth.

Where Pith is reading between the lines

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

  • The approach may generalize to determine chromatic profiles for higher r or higher chromatic numbers.
  • Vertex-extendability could apply to other problems involving coloring after small modifications.
  • Testing the reduction on non-critical graphs would check its robustness.

Load-bearing premise

The equality δ_χ(H,2) equals the maximum of the odd-cycle chromatic threshold and the vertex-extendable threshold holds for all color-critical 3-chromatic graphs.

What would settle it

A color-critical graph H with χ(H)=3 whose computed δ_χ(H,2) is not equal to the max of δ_χ(C_{2k+1},2) and δ_ext(H,2), or lies outside the eight values.

Figures

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

Figure 1
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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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.

Referee Report

0 major / 2 minor

Summary. The manuscript resolves the chromatic profile δ_χ(H,2) for every graph 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} and supplies a complete structural characterization of the realizing graphs H. The proof introduces the auxiliary vertex-extendable threshold δ_ext(H,r) and establishes the structural reduction δ_χ(H,2) = max{δ_χ(C_{2k+1},2), δ_ext(H,2)} for color-critical H with odd girth 2k+1 (k≥2). It further extends the classical triangle case to all such color-critical graphs.

Significance. This work resolves a concrete case of the open Problem 45 posed by Allen, Böttcher, Griffiths, Kohayakawa, and Morris, which was described as expected to be difficult. The explicit finite list together with the structural characterization constitutes a substantial advance in extremal graph theory. The newly defined parameter δ_ext(H,r), motivated by the vertex-extendability framework of Liu, Mubayi, and Reiher, is a clean and potentially reusable tool. The structural reduction theorem is a load-bearing contribution that converts the original parameter into quantities that can be classified by odd girth and minimal non-extendable graphs.

minor comments (2)
  1. The abstract states the key equality but does not spell out the definition of δ_ext(H,r) in a single sentence; adding a brief parenthetical would improve accessibility for readers who have not yet reached the definitions section.
  2. In the classification of δ_ext values, the case distinctions on odd girth are clear, but a short table summarizing which graphs realize each rational would help readers quickly verify the completeness claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the main results, and recommendation to accept. We appreciate the recognition that the work resolves Problem 45 in the case r=2 for all graphs H with chromatic number 3, along with the introduction of the vertex-extendable threshold and the structural reduction theorem.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper proves the central structural reduction δ_χ(H,2) = max{δ_χ(C_{2k+1},2), δ_ext(H,2)} directly from the definitions of the two parameters for color-critical H; δ_ext is introduced as a new auxiliary quantity rather than fitted to the target result, and δ_χ(C_{2k+1},2) is treated as an independently known or computable base case for odd cycles. The subsequent classification of δ_ext values proceeds by case analysis on odd girth and minimal non-extendable graphs without reducing back to the original δ_χ by construction. No self-citation chain, ansatz smuggling, or renaming of known results is load-bearing for the finite-set claim. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper works entirely within standard graph-theoretic axioms (simple undirected graphs, chromatic number, minimum degree, forbidden subgraphs). The only new object introduced is the vertex-extendable threshold δ_ext(H,r), which is defined rather than postulated as an independent entity. No free parameters are fitted to data; all thresholds are derived combinatorially.

axioms (1)
  • standard math Standard definitions of chromatic number χ(H), odd girth g_odd(H), color-critical graphs, and H-free graphs.
    Invoked throughout the abstract as background for the chromatic profile definition.
invented entities (1)
  • vertex-extendable threshold δ_ext(H,r) no independent evidence
    purpose: Auxiliary parameter that measures the density threshold at which a single vertex v with χ(G-v)≤r forces the whole H-free graph to be r-colorable.
    Defined in the abstract as a new tool motivated by Liu-Mubayi-Reiher vertex-extendability; used to obtain the key reduction formula.

pith-pipeline@v0.9.0 · 6045 in / 1755 out tokens · 54350 ms · 2026-05-21T09:39:28.947872+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · 2 internal anchors

  1. [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

    work page 2013

  2. [2]

    Alon and C

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

    work page 2016

  3. [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

    work page 1974

  4. [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. [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

    work page 2005

  6. [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

    work page 2023

  7. [7]

    Caro and Z

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

    work page 2020

  8. [8]

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

    work page 1997

  9. [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

    work page 1966

  10. [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

    work page 1973

  11. [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

    work page 1946

  12. [12]

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

    work page 2026

  13. [13]

    Goddard and J

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

    work page 2011

  14. [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

    work page 1982

  15. [15]

    Illingworth

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

    work page 2022

  16. [16]

    Illingworth

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

    work page 2022

  17. [17]

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

    work page 1995

  18. [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. [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

    work page 1954

  20. [20]

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

    work page 2023

  21. [21]

    Coloring dense graphs via VC-dimension

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

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  22. [22]

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

    work page 2016

  23. [23]

    Chromatic number and mimimum degree of K_r-free graphs

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

    work page internal anchor Pith review Pith/arXiv arXiv 2070

  24. [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

    work page 1976

  25. [25]

    Thomassen

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

    work page 2007

  26. [26]

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

    work page 1941

  27. [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. [28]

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

    work page arXiv 2024

  29. [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) ....

    work page 2024