arxiv: 2605.10897 · v1 · submitted 2026-05-11 · 🧮 math.CO

Recognition: no theorem link

Chromatic thresholds for pairs of graphs

Jun Gao , Hong Liu , Zhuo Wu , Yisai Xue

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:44 UTC · model grok-4.3

classification 🧮 math.CO

keywords chromatic thresholdRamsey theory3-chromatic graphsminimum degree conditionsedge coloringforbidden subgraphsRamsey configurationsgraph coloring

0 comments

The pith

For any pair of 3-chromatic graphs, the two-color Ramsey chromatic threshold equals exactly one of five densities, classified by ordinary thresholds and embeddability into C5-type configurations.

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

The paper determines the minimum degree density that forces bounded chromatic number in any graph that can be edge-colored without a red copy of H1 or a blue copy of H2. It focuses on the case where both H1 and H2 are 3-chromatic and shows that this Ramsey-style threshold is always one of five explicit fractions. A sympathetic reader would care because the result reduces what might have been an open-ended family of problems to a short, computable list based on familiar properties of the input graphs.

Core claim

For any two 3-chromatic graphs H1 and H2, the minimum-degree density above which every graph that admits a red-blue edge-coloring with no red H1 and no blue H2 has bounded chromatic number is exactly one of 2/3, 5/7, 3/4, 7/9, or 4/5. The precise value for each pair is fixed by the ordinary chromatic thresholds of H1 and H2 together with whether each graph embeds into a hierarchy of C5-type Ramsey configurations.

What carries the argument

The two-color Ramsey chromatic threshold for a pair (H1, H2), which is the infimum density such that minimum-degree conditions plus the existence of an (H1, H2)-free coloring imply bounded chromatic number, classified via ordinary chromatic thresholds and embeddability into C5-type Ramsey configurations.

If this is right

Every pair of 3-chromatic graphs falls into one of the five threshold classes.
The ordinary chromatic threshold of each graph is an input that narrows the possible Ramsey thresholds.
Embeddability into C5-type configurations decides the exact value when the ordinary thresholds alone leave ambiguity.
The result supplies an exhaustive dictionary that assigns the correct threshold to any given 3-chromatic pair.

Where Pith is reading between the lines

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

The same configuration hierarchy may produce only finitely many thresholds for pairs with higher chromatic number.
The five densities likely arise from successive ratio-symmetric relations among the C5-type configurations.
Explicit constructions of the C5-type configurations could be used to test embeddability for concrete families such as odd wheels or other 3-chromatic graphs.

Load-bearing premise

The complete classification assumes that embeddability of any 3-chromatic graph into the hierarchy of C5-type Ramsey configurations can be decided independently of the threshold calculation itself.

What would settle it

A single pair of 3-chromatic graphs whose two-color Ramsey chromatic threshold is not one of 2/3, 5/7, 3/4, 7/9, 4/5 or whose value fails to match the prediction from their ordinary thresholds and embeddability status.

Figures

Figures reproduced from arXiv: 2605.10897 by Hong Liu, Jun Gao, Yisai Xue, Zhuo Wu.

**Figure 1.1.** Figure 1.1: Decision diagram for δχpH1, H2q when χpHiq “ 3. Here η “ maxtδχpH1q, δχpH2qu. The right-hand branch applies when neither graph embeds into C5; the left-hand branch applies when at least one graph embeds into C5, or when both graphs have embeddability 3. Even in the symmetric case H1 “ H2 “ H, the classification is already rich. The following table of examples illustrates the possible behaviors. We refer … view at source ↗

**Figure 3.1.** Figure 3.1: Families Z0, Z1 and Z2. One can think of the subscript i P t0, 1, 2u in Zi as the number of Zykov graphs used to replace blowup of edges in C5 (which is the number of dashed edges in the figure). Given a graph H and a family of graphs H, we say H embeds into H, denoted by H ãÑ H, if H is a subgraph of some graph in H. It is not hard to see that H ãÑ C5 ùñ H ãÑ Z2 ùñ H ãÑ Z1 ùñ H ãÑ Z0. We can now define … view at source ↗

**Figure 3.** Figure 3: ) [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

**Figure 3.3.** Figure 3.3: Petersen graph Proposition 3.4. δχpC ˚ 10r3sq “ 1{3. Proof. Let H “ C ˚ 10r3s, X “ Ť5 i“1 Xi , and Y “ Ť5 i“1 Yi , with subscripts taken modulo 5. The graph H has a proper 3-coloring in which X is one color class and HrY s is colored with the other two colors. Since H contains an odd cycle, this is an optimal coloring. Deleting the color class X leaves HrY s, which is a forest. Hence MpHq contains a fore… view at source ↗

**Figure 3.4.** Figure 3.4: Families B1 and B2 The following proposition shows that if a small graph embeds into B1 (B2 resp.), then it can also be embedded into some graph in Z1 (Z2 resp.). Proposition 3.7. Let H be a graph with χpHq ď 3 and i P t1, 2u. If H Ď Bipn, k, ℓq with ℓ ą |H|, then H ãÑ Zi. Proof. We prove the case i “ 1 first. Let V pB1pn, k, ℓqq “ U 1 Y W Y Z1 Y Z2 Y Z3. Suppose B1pn, k, ℓq contains a copy of H, say H˚ … view at source ↗

**Figure 3.7.** Figure 3.7: The graph G3 Construction 1. Let G1 be an n-vertex graph on vertex set Ť iPr5s Vi obtained as follows. • Start with a complete 5-partite graph on pV1, V2, V3, V4, V5q with Ramsey coloring of K5 and |Vi | “ n{5 for i P r5s. • Embed an n{5-vertex pk, ℓq-Erd˝os graph into V1 and color all its edges red. Then δpG1 q “ 4n{5 and χpG1 q ě k. Property (G1 ). If H1 ãÑ Z0 and H2 ãÑ C5, then G1 r is H1-free and G… view at source ↗

**Figure 3.10.** Figure 3.10: The graph G6 Construction 4. Let G4 be an n-vertex graph on vertex set Ť iPr4s Vi obtained as follows. • Start with a complete 4-partite graph on pV1, V2, V3, V4q, where the edges between V1 and V2, and between V3 and V4, are colored red, and all other edges blue, with |Vi | “ n{4 for i P r4s. • Embed an n{4-vertex pk, ℓq-Erd˝os graph into V1 and color all its edges red. Then δpG4 q “ 3n{4 and χpG4 q ě … view at source ↗

**Figure 4.1.** Figure 4.1: Embed H into G The proofs of (ii) and (iii) follow analogously, with the same choice of the auxiliary constants q " t0 " |H|, invoking Lemma 4.7(iii) and (i), respectively. 4.2 Proof of Lemma 4.6 To prove Lemma 4.6, it suffices to show that there exists α :“ αpε, d, tq with the following property: • for any X Ď V1 with |X| ě ε|V1|, there exist S Ď X of size |S| “ α|V1| and an pα, εq-partition V4 “ T0 YT1… view at source ↗

**Figure 4.2.** Figure 4.2: An illustration of the proof of Lemma 4.6 [PITH_FULL_IMAGE:figures/full_fig_p015_4_2.png] view at source ↗

**Figure 5.1.** Figure 5.1: Illustrations of Cases 2 and 3. Case 3. fpH1, H2q “ 3{4. In this case, both H1, H2 ãÑ Z1. By Claim 5.7, we have |I ˚ b | ď 1 2 k, while we have |I 1 r | ` |I ˚ b | ě p 1 2 ` γ 2 qk by Claim 5.8. Hence, I 1 r ‰ ∅. Claim 5.10. For any vertex v P I 1 r , v has no red neighbors in I ˚ b . Proof of claim. Suppose to the contrary that there exists a red edge v1v2 P EpRrq with v1 P I 1 r and v2 P I ˚ b . As v2 … view at source ↗

read the original abstract

The chromatic threshold of a graph $H$ is the minimum-degree density above which every $H$-free graph has bounded chromatic number. We study a two-color Ramsey analogue: for graphs $H_1$ and $H_2$, we ask for the minimum-degree density above which every graph that admits a red-blue edge-coloring with no red copy of $H_1$ and no blue copy of $H_2$ has bounded chromatic number. We give a complete answer when both $H_1$ and $H_2$ are 3-chromatic. The threshold takes exactly one of the five values \[ \frac23,\quad \frac57,\quad \frac34,\quad \frac79,\quad \frac45, \] and we characterize precisely which pairs $(H_1,H_2)$ give each value. The classification is determined by the ordinary chromatic thresholds of $H_1$ and $H_2$ and by their embeddability into a hierarchy of $C_5$-type Ramsey configurations.

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 fully classifies the two-color Ramsey chromatic threshold for every pair of 3-chromatic graphs into one of five explicit values.

read the letter

The punchline is that this paper resolves the two-color Ramsey chromatic threshold problem for all pairs of 3-chromatic graphs. It shows the threshold is always exactly one of five values—2/3, 5/7, 3/4, 7/9, or 4/5—and gives a precise characterization of which pairs produce each one based on the ordinary chromatic thresholds plus embeddability into C5-type Ramsey configurations. This is genuinely new. The single-graph chromatic threshold does not immediately imply the pair result, so the authors had to develop the right framework. They do this well by linking the value to the ordinary chromatic thresholds of each graph and to their embeddability into a hierarchy of C5-type configurations. This approach organizes the different behaviors without introducing extra parameters. The soft spots are limited. The result is stated only for 3-chromatic graphs, leaving higher cases open, but that is not a flaw since the abstract is clear about the scope. The classification depends on determining embeddability independently, which the paper presumably handles through case analysis. If that analysis is thorough and without gaps, the argument is solid. There is no sign of circularity or invented entities. This paper is for researchers in extremal graph theory and Ramsey theory who are interested in degree conditions that force bounded chromatic number under colorings. A reader familiar with chromatic thresholds will see how the pair version fits into the existing picture and get concrete values to work with. It deserves a serious referee because it delivers a full answer to a natural question with an explicit classification. I recommend sending it out for peer review.

Referee Report

0 major / 3 minor

Summary. The paper defines the two-color chromatic threshold for a pair of graphs (H1, H2) as the infimum over densities δ such that every n-vertex graph G with minimum degree at least δn that admits a red-blue edge-coloring with no red copy of H1 and no blue copy of H2 must have bounded chromatic number. For the case in which both H1 and H2 are 3-chromatic, the authors claim a complete classification: the threshold equals exactly one of the five values 2/3, 5/7, 3/4, 7/9 or 4/5, and they characterize precisely which pairs realize each value in terms of the ordinary (one-color) chromatic thresholds of H1 and H2 together with their embeddability into a stated hierarchy of C5-type Ramsey configurations.

Significance. If the classification is correct, the result supplies an exhaustive resolution of the two-color chromatic-threshold problem in the 3-chromatic case, extending the single-graph theory by exhibiting an explicit finite list of attainable densities and a structural criterion (embeddability) that determines the value for every pair. The explicit linkage between the pair threshold and the individual chromatic thresholds plus the C5-type configurations provides a concrete, falsifiable description that could serve as a template for analogous questions with more colors or higher chromatic numbers.

minor comments (3)

The abstract and introduction refer to 'a hierarchy of C5-type Ramsey configurations' without giving an immediate definition or forward reference; a one-sentence description of the relevant constructions (or a pointer to the section where they are introduced) would make the characterization statement self-contained for readers who have not yet reached the technical sections.
Notation for the two-color threshold (presumably denoted something like δ_χ(H1,H2) or similar) should be introduced explicitly in the first paragraph of the introduction, together with a brief comparison to the ordinary chromatic threshold δ_χ(H), to avoid any ambiguity when the classification is stated.
The statement that the classification is 'determined by the ordinary chromatic thresholds of H1 and H2 and by their embeddability' would benefit from an explicit sentence listing the five cases and the precise embeddability conditions that distinguish them, even if the full proof appears later.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive summary of our manuscript and for recommending minor revision. We address the referee's summary below.

read point-by-point responses

Referee: The paper defines the two-color chromatic threshold for a pair of graphs (H1, H2) as the infimum over densities δ such that every n-vertex graph G with minimum degree at least δn that admits a red-blue edge-coloring with no red copy of H1 and no blue copy of H2 must have bounded chromatic number. For the case in which both H1 and H2 are 3-chromatic, the authors claim a complete classification: the threshold equals exactly one of the five values 2/3, 5/7, 3/4, 7/9 or 4/5, and they characterize precisely which pairs realize each value in terms of the ordinary (one-color) chromatic thresholds of H1 and H2 together with their embeddability into a stated hierarchy of C5-type Ramsey configurations.

Authors: We agree with this summary of our results. The manuscript does indeed provide a complete classification for the two-color chromatic threshold when both graphs are 3-chromatic, with the threshold being precisely one of 2/3, 5/7, 3/4, 7/9, or 4/5, determined by the individual chromatic thresholds and the embeddability into the hierarchy of C5-type configurations. revision: no

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central result is an explicit classification of the two-color chromatic threshold for 3-chromatic pairs (H1, H2) into one of five explicit density values, with each pair assigned according to the independent ordinary chromatic thresholds of H1 and H2 together with the independently verifiable structural property of embeddability into a stated hierarchy of C5-type Ramsey configurations. No derivation step equates a claimed prediction to a fitted parameter by construction, renames a known result, or reduces the classification to a self-citation whose content is itself defined by the present work. The ordinary thresholds and embeddability checks are external inputs whose evaluation does not presuppose the target threshold values, rendering the derivation self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the paper introduces no free parameters or new entities; it relies on standard graph-theoretic definitions and the pre-existing notion of chromatic threshold for single graphs.

axioms (2)

standard math Standard definitions of chromatic number, minimum-degree density, H-free graphs, and edge-colorings avoiding monochromatic copies
These are foundational concepts invoked to define the new threshold.
domain assumption Existence and well-definedness of ordinary chromatic thresholds for individual 3-chromatic graphs
The classification uses these as inputs to determine the pair threshold.

pith-pipeline@v0.9.0 · 5478 in / 1544 out tokens · 45636 ms · 2026-05-12T03:44:42.598554+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

Allen, J

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

work page 2013
[2]

P. Erd˝ os. Graph theory and probability.Canadian Journal of Mathematics, 11:34–38, 1959

work page 1959
[3]

Erd˝ os and M

P. Erd˝ os and M. Simonovits. On a valence problem in extremal graph theory.Discrete Mathe- matics, 5(4):323–334, 1973

work page 1973
[4]

Goddard and J

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

work page 2011
[5]

Hoeffding

W. Hoeffding. Probability inequalities for sums of bounded random variables.Journal of the American Statistical Association, 58(301):13–30, 1963

work page 1963
[6]

Huang, H

X. Huang, H. Liu, M. Rong, and Z. Xu. Interpolating chromatic and homomorphism thresholds. arXiv preprint arXiv:2502.09576, 2025

work page arXiv 2025
[7]

J. Kim, Y. Kim, and H. Liu. Two conjectures in ramsey–tur´ an theory.SIAM Journal on Discrete Mathematics, 33(1):564–586, 2019

work page 2019
[8]

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

work page arXiv 2026
[9]

Koml´ os and M

J. Koml´ os and M. Simonovits. Szemer´ edi’s regularity lemma and its applications in graph theory, In: Combinatorics, Paul Erd˝ os is eighty, vol. 2 (Keszthely, 1993). volume 2 of Bolyai Soc. Math. Stud., pp. 295–352. J´ anos Bolyai Math. Soc., Budapest, 1996

work page 1993
[10]

H. Liu, C. Shangguan, J. Skokan, and Z. Xu. Beyond chromatic threshold via the pp, qq-theorem, and a sharp blow-up phenomenon.arXiv preprint arXiv:2403.17910, 2024

work page arXiv 2024
[11]

H. Liu, Z. Wu, N. Yang, and S. Zhang. Chromatic thresholds for linear equations and recurrence. arXiv preprint arXiv:2603.05490, 2026

work page arXiv 2026
[12]

Luczak and S

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

work page arXiv 2010
[13]

Nikiforov

V. Nikiforov. Chromatic number and minimum degree of Kr-free graphs.arXiv:1001.2070, 2010

work page arXiv 2070
[14]

Thomassen

C. Thomassen. On the chromatic number of triangle-free graphs of large minimum degree. Combinatorica, 22(4):591–596, 2002. 25

work page 2002