arxiv: 2605.08848 · v1 · submitted 2026-05-09 · 🧮 math.CO

Recognition: no theorem link

Ramsey-type chi-bounds for chi-bounded graph classes

Sang-il Oum, Tung Nguyen

Pith reviewed 2026-05-12 01:26 UTC · model grok-4.3

classification 🧮 math.CO

keywords χ-boundednessinduced subgraphsRamsey numbersforestscomplete multipartite graphschromatic numberlinear boundsbroom graphs

0 comments

The pith

Graphs with no induced forest T of broom components and no induced complete multipartite H satisfy χ(G) ≤ C · R(α(H), ω(G)+1) for constant C depending only on T and H.

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

The paper proves that forbidding an induced path together with an induced four-cycle makes a graph class linearly χ-bounded. It then shows the same style of bound holds more generally whenever the forbidden forest T has only broom components and H is any complete multipartite graph, or whenever T is an arbitrary forest and H is complete bipartite. These conditions unify many earlier linear and polynomial χ-boundedness theorems for induced-subgraph-free classes. The work also supplies a new, quantitatively improved proof that any fixed tree appears as an induced subgraph in graphs obeying certain sparsity conditions.

Core claim

For every path P, the class of graphs with no induced P and no induced four-cycle C4 is linearly χ-bounded. More generally, when every component of T is a broom and H is complete multipartite, or when T is a forest and H is complete bipartite, every graph G with no induced T and no induced H has chromatic number at most C · R(α(H), ω(G)+1) for some constant C depending only on T and H.

What carries the argument

The Ramsey number R(α(H), ω(G)+1) applied to graphs whose forbidden induced subgraphs T and H obey the broom-component or complete-bipartite restrictions.

If this is right

The class of induced-P-and-C4-free graphs is linearly χ-bounded.
Many earlier linear and polynomial χ-boundedness results for specific forbidden induced subgraphs now follow from a single pair of structural conditions on T and H.
Any fixed tree appears as an induced subgraph in graphs satisfying the stated sparsity conditions, with quantitatively improved bounds.
The same Ramsey-type bound applies uniformly to all complete multipartite H when T has only broom components.

Where Pith is reading between the lines

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

The same technique may extend to other tree shapes beyond brooms, producing similar bounds for wider families of forbidden forests.
If the bound can be shown for arbitrary complete multipartite H without the broom restriction, several remaining cases of the χ-boundedness conjecture for induced-hereditary classes would be settled.
The existence of an explicit constant C would immediately yield polynomial-time coloring algorithms once an oracle for the relevant Ramsey numbers is available.
The sparsity-to-induced-tree result suggests new detection algorithms for induced trees inside graphs of bounded average degree.

Load-bearing premise

The forbidden induced subgraphs T and H must obey the broom-component or complete-bipartite structural restrictions for the Ramsey bound to hold.

What would settle it

A single graph G with no induced T and no induced H (under the paper's conditions on T and H) whose chromatic number exceeds every constant C times R(α(H), ω(G)+1).

Figures

Figures reproduced from arXiv: 2605.08848 by Sang-il Oum, Tung Nguyen.

**Figure 1.** Figure 1: The (8, 5)-broom. class G admits a χ-binding function x 7→ C · R(s, x + 1), where C = C(G, m,s) ≥ 1. Again, such a general Ramsey-type extension could actually hold for all χ-bounded classes, as follows. Conjecture 1.3. For every χ-bounded class G and every two integers m,s ≥ 1, there exists C = C(G, m,s) ≥ 1 such that every mKs -free graph G ∈ G satisfies χ(G) ≤ C · R(s, ω(G) + 1). Indeed, Conjecture 1.2 … view at source ↗

**Figure 2.** Figure 2: An illustration of the proof of Theorem 2.1. Subproof. Suppose that |Z| ≥ R(s, ω + 1). Then Z contains a stable set S of size s. Thus χ(L \ ( T v∈S NG(v))) ≤ bs, which implies χ L V(L) ∩ \ v∈S NG(v) ≥ χ(L) − bs > f (p) − 2a − bs = q, contrary to the hypothesis. This proves Claim 2.1.2. □ Now, since J is R(s,ω + 1)-connected, |V(J) ∩ NG(vp )| ≥ R(s,ω + 1), and |V(L)| ≥ R(s,ω + 1), Claim 2.1.2 gives a… view at source ↗

read the original abstract

We prove that for every path $P$, the class of graphs with no induced $P$ and no induced four-cycle $C_4$ is linearly $\chi$-bounded. More generally, we ask for which pairs $\{T,H\}$ where $T$ is a forest and $H$ is a complete multipartite graph, every graph $G$ with no induced $T$ and no induced $H$ has chromatic number at most $C \cdot R(\alpha(H),\omega(G)+1)$ for some constant $C$ depending only on $T$ and $H$, where $R(\cdot,\cdot)$ denotes the usual Ramsey numbers. We show that this holds in the following two instances, which strengthen the case $T=P$ and $H=C_4$ mentioned above: (1) every component of $T$ is a broom and $H$ is complete multipartite; or (2) $T$ is a forest and $H$ is complete bipartite. These two unify and substantially extend a number of previous results on linear and polynomial $\chi$-boundedness for various graph classes. For case (2), we also provide a new proof (with better bounds) of a recent result of Fox, Nenadov, and Pham on the existence of an induced copy of a fixed tree in a graph satisfying certain sparsity conditions.

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

The paper gives two new families of (T,H) pairs where induced-(T,H)-free graphs satisfy a Ramsey-type χ-bound that yields linear boundedness in the path-plus-C4 case and unifies earlier results.

read the letter

The paper proves that graphs without an induced path and without an induced C4 are linearly χ-bounded. More broadly, it identifies two families of forbidden pairs (T forest, H multipartite) where the chromatic number is bounded by a constant times the Ramsey number R(α(H), ω(G)+1). This covers broom-component forests with multipartite H and arbitrary forests with bipartite H. These cases are new and stronger than previous path and C4 results. The work unifies a number of earlier theorems on linear and polynomial χ-boundedness. It also gives a new proof with improved bounds for embedding a fixed induced tree in sparse graphs, building on Fox, Nenadov, and Pham. The arguments rely on Ramsey numbers as a black box and standard techniques for induced subgraphs. This keeps things non-circular and recovers old results as special cases. For bipartite H, the bound is polynomial in ω when α(H) is fixed. A minor limitation is that the constants C are not computed explicitly and depend on the structure of T and H, which is typical but means the results are more existential than quantitative for large T. The tree embedding improvement is presented as better, but the exact gain would need comparison to the original paper. Readers in combinatorial graph theory, especially those studying χ-bounded classes and Ramsey theory applications, will find this useful. It advances the understanding of which hereditary classes are χ-bounded and provides tools for coloring problems in those classes. The paper is coherent and engages the literature properly, so it merits a serious referee. I would recommend putting it through peer review. The new cases and the proof technique look like they add real value to the field.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that for every path P, the class of graphs with no induced P and no induced C4 is linearly χ-bounded. More generally, it establishes Ramsey-type bounds χ(G) ≤ C · R(α(H), ω(G)+1) (with C depending only on T and H) for induced-(T,H)-free graphs in two cases: (1) every component of the forest T is a broom and H is complete multipartite; (2) T is any forest and H is complete bipartite. It also supplies a new proof, with improved bounds, of the existence of an induced copy of a fixed tree in graphs satisfying certain sparsity conditions, strengthening a result of Fox, Nenadov, and Pham. These results unify and extend prior work on χ-boundedness for various induced-subgraph-free classes.

Significance. If the proofs are correct, the work provides a clean, explicit framework for χ-boundedness that recovers linear bounds as special cases (e.g., when α(H)=2) and uses standard Ramsey numbers only as a black-box multiplier. The parameter-free nature of the constants C (depending solely on the fixed T and H) and the new tree-embedding argument are notable strengths. The results substantially extend the catalog of classes known to be χ-bounded with good quantitative bounds.

minor comments (2)

Abstract: the sentence 'we ask for which pairs {T,H} ...' could be rephrased to 'we determine for which pairs' or 'we resolve the question for the following two families of pairs' to better reflect that the paper settles the question in two broad cases rather than leaving it open.
The claim of 'better bounds' for the induced-tree result (relative to Fox–Nenadov–Pham) should be made quantitative, e.g., by stating the explicit improvement in the dependence on the sparsity parameter or on the tree size.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of the manuscript. The recommendation for minor revision is appreciated, and the provided summary accurately reflects the main results and their context within the literature on χ-boundedness.

Circularity Check

0 steps flagged

No significant circularity; bounds use external Ramsey numbers as black-box multipliers

full rationale

The derivation establishes upper bounds χ(G) ≤ C · R(α(H), ω(G)+1) for induced-(T,H)-free graphs under explicit structural restrictions on the fixed forbidden pair (T forest with broom components or arbitrary forest; H complete multipartite or bipartite). These rely on standard, externally defined Ramsey numbers R(·,·) and known properties such as α(C4)=2 implying R(2,ω(G)+1)=ω(G)+1 for the linear case. The two main cases and the new proof of the Fox-Nenadov-Pham result are proved directly via graph-theoretic arguments that do not reduce to self-citations, fitted parameters, or self-definitional loops. Prior results appear only as recovered corollaries. No load-bearing step collapses to an input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rely on the existence and basic properties of Ramsey numbers together with standard facts about induced subgraphs and chromatic numbers; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (2)

standard math Ramsey numbers R(s,t) exist and are finite for all positive integers s,t
Invoked when bounding χ(G) by R(α(H), ω(G)+1)
domain assumption Basic properties of induced subgraphs and chromatic number in hereditary classes
Used throughout the statements about forbidden induced T and H

pith-pipeline@v0.9.0 · 5546 in / 1455 out tokens · 38129 ms · 2026-05-12T01:26:18.463355+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

59 extracted references · 59 canonical work pages · 1 internal anchor

[1]

M.Ajtai,J.Komlós,andE.Szemerédi.AnoteonRamseynumbers.J.Combin.TheorySer.A,29(3):354–360,1980.4

work page 1980
[2]

Brause, M

C. Brause, M. Geiß er, and I. Schiermeyer. Homogeneous sets, clique-separators, critical graphs, and optimalχ- bindingfunctions.DiscreteAppl.Math.,320:211–222,2022.3

work page 2022
[3]

M.Briański,J.Davies,andB.Walczak.Separatingpolynomialχ-boundednessfromχ-boundedness.Combinatorica, 44(1):1–8,2024.2

work page 2024
[4]

Cameron, S

K. Cameron, S. Huang, and O. Merkel. An optimalχ-bound for (P6, diamond)-free graphs.J. Graph Theory, 97(3):451–465,2021.4

work page 2021
[5]

K.Cameron,S.Huang,I.Penev,andV.Sivaraman.Theclassof(P 7,C 4,C 5)-freegraphs: decomposition,algorithms, andχ-boundedness.J.GraphTheory,93(4):503–552,2020.4

work page 2020
[6]

A.CharandT.Karthick.Coloringof(P 5,4-wheel)-freegraphs.DiscreteMath.,345(5):PaperNo.112795,22,2022.4

work page 2022
[7]

Char and T

A. Char and T. Karthick.χ-boundedness and related problems on graphs without long induced paths: A survey. DiscreteAppl.Math.,364:99–119,2025.3

work page 2025
[8]

A.CharandT.Karthick.OngraphswithnoinducedP 5 orK 5 −e.J.GraphTheory,110(1):5–22,2025.3

work page 2025
[9]

R.ChenandB.Xu.Structureandlinear-pollyannaforsomesquare-freegraphs.DiscreteMathematics,349(6):114979, June2026.2

work page
[10]

S.A.Choudum,T.Karthick,andM.A.Shalu.Perfectcoloringandlinearlyχ-boundP 6-freegraphs.J.GraphTheory, 54(4):293–306,2007.4

work page 2007
[11]

Chudnovsky, L

M. Chudnovsky, L. Cook, J. Davies, and S. Oum. Reunitingχ-boundedness with polynomialχ-boundedness.J. Combin.TheorySer.B,176:30–73,2026.2,17

work page 2026
[12]

Chudnovsky, S

M. Chudnovsky, S. Huang, T. Karthick, and J. Kaufmann. Square-free graphs with no induced fork.Electron. J. Combin.,28(2):PaperNo.2.20,16,2021.4

work page 2021
[13]

Chudnovsky, I

M. Chudnovsky, I. Penev, A. Scott, and N. Trotignon. Substitution andχ-boundedness.J. Combin. Theory Ser. B, 103(5):567–586,2013.17

work page 2013
[14]

Chudnovsky, N

M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem.Ann. of Math. (2), 164(1):51–229,2006.2

work page 2006
[15]

M.Chudnovsky,A.Scott,andP.Seymour.Excludingpairsofgraphs.J.Combin.TheorySer.B,106:15–29,2014.4

work page 2014
[16]

Chudnovsky, A

M. Chudnovsky, A. Scott, and P. Seymour. Induced subgraphs of graphs with large chromatic number. III. Long holes.Combinatorica,37(6):1057–1072,2017.2

work page 2017
[17]

Chudnovsky and P

M. Chudnovsky and P. Seymour. Even-hole-free graphs still have bisimplicial vertices.J. Combin. Theory Ser. B, 161:331–381,2023.2,11

work page 2023
[18]

Conforti, G

M. Conforti, G. Cornuéjols, and K. Vušković. Square-free perfect graphs.J. Combin. Theory Ser. B, 90(2):257–307, 2004.2

work page 2004
[19]

Davies and Y

J. Davies and Y. Yuditsky. Polynomial Gyárfás–Sumner conjecture for graphs of bounded boxicity.Innov. Graph Theory,3:37–48,2026.11

work page 2026
[20]

W. Dong, B. Xu, and Y. Xu. On the chromatic number of someP5-free graphs.Discrete Math., 345(10):Paper No. 113004,11,2022.4

work page 2022
[21]

X.DuandR.McCarty.Asurveyofdegree-boundedness.EuropeanJ.Combin.,129:PaperNo.104092,26,2025.8,9

work page 2025
[22]

P.Erdős.Graphtheoryandprobability.Canad.J.Math.,11:34–38,1959.17

work page 1959
[23]

Fiala and J

J. Fiala and J. Kratochvíl. Locally constrained graph homomorphisms—structure, complexity, and applications. ComputerScienceReview,2(2):97–111,2008.11

work page 2008
[24]

J.-L.Fouquet,V.Giakoumakis,F.Maire,andH.Thuillier.OngraphswithoutP 5and P 5.DiscreteMath.,146(1-3):33– 44,1995.3

work page 1995
[25]

J. Fox, R. Nenadov, and H. T. Pham. The largest subgraph without a forbidden induced subgraph.Combinatorica, 45(6):PaperNo.60,27,2025.5,9,11

work page 2025
[26]

S.GaspersandS.Huang.Linearlyχ-bounding(P 6,C 4)-freegraphs.J.GraphTheory,92(3):322–342,2019.4

work page 2019
[27]

IMRN,(4):PaperNo.rnaf025,23,2025.9

A.GirãoandZ.Hunter.InducedsubdivisionsinK s,s-freegraphswithpolynomialaveragedegree.Int.Math.Res.Not. IMRN,(4):PaperNo.rnaf025,23,2025.9

work page 2025
[28]

Girão and B

A. Girão and B. Narayanan. Subgraphs of large connectivity and chromatic number.Bull. Lond. Math. Soc., 54(3):868–875,2022.6

work page 2022
[29]

J.Goedgebeur,S.Huang,Y.Ju,andO.Merkel.Colouringgraphswithnoinducedsix-vertexpathordiamond.The- oret.Comput.Sci.,941:278–299,2023.4

work page 2023
[30]

Gravier, C

S. Gravier, C. T. Hoàng, and F. Maffray. Coloring the hypergraph of maximal cliques of a graph with no long path. DiscreteMath.,272(2-3):285–290,2003.3

work page 2003
[31]

A. Gyárfás. On Ramsey covering-numbers. InInfinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, pages 801–816. Colloq. Math. Soc. Janós Bolyai, Vol. 10. North-Holland, Amsterdam, 1975.1,4

work page 1973
[32]

A. Gyárfás. Problems from the world surrounding perfect graphs. InProceedingsoftheInternationalConferenceon CombinatorialAnalysisanditsApplications(Pokrzywna,1985),volume19,pages413–441(1988),1987.3,6

work page 1985
[33]

Gyárfás, E

A. Gyárfás, E. Szemerédi, and Z. Tuza. Induced subtrees in graphs of large chromatic number.Discrete Math., 30(3):235–244,1980.4

work page 1980
[34]

C.T.Hoàng.Onthestructureofperfectlydivisiblegraphs.DiscreteMath.,349(2):PaperNo.114809,5,2026.4

work page 2026
[35]

S.Huang.Theoptimalχ-boundfor(P 7,C 4,C 5)-freegraphs.DiscreteMath.,347(7):PaperNo.114036,14,2024.4 RAMSEY-TYPEχ-BOUNDS FORχ-BOUNDED GRAPH CLASSES 19

work page 2024
[36]

Huang, Y

S. Huang, Y. Zhou, and Y. Chang. The optimal chromatic bound for even-hole-free graphs without induced seven- vertexpaths.arXiv:2602.04403.4

work page arXiv
[37]

Hunter, A

Z. Hunter, A. Milojević, B. Sudakov, and I. Tomon.C4-free subgraphs of high degree with geometric applications. arXiv:2506.23942.9

work page arXiv
[38]

Karthick and F

T. Karthick and F. Maffray. Square-free graphs with no six-vertex induced path.SIAM J. Discrete Math., 33(2):874– 909,2019.4

work page 2019
[39]

T.KarthickandS.Mishra.Onthechromaticnumberof(P 6,diamond)-freegraphs.GraphsCombin.,34(4):677–692, 2018.4

work page 2018
[40]

1994.4,9

H.A.KiersteadandS.G.Penrice.Radiustwotreesspecifyχ-boundedclasses.J.GraphTheory,18(2):119–129,Mar. 1994.4,9

work page 1994
[41]

J. H. Kim. The Ramsey numberR(3,t)has order of magnitudet2/logt.Random Structures Algorithms, 7(3):173– 207,1995.3

work page 1995
[42]

D.KühnandD.Osthus.InducedsubdivisionsinK s,s-freegraphsoflargeaveragedegree.Combinatorica,24(2):287– 304,2004.9

work page 2004
[43]

Y.Li,C.C.Rousseau,andW.Zang.AsymptoticupperboundsforRamseyfunctions.GraphsCombin.,17(1):123–128, 2001.4

work page 2001
[44]

X.Liu,J.Schroeder,Z.Wang,andX.Yu.Polynomialχ-bindingfunctionsfort-broom-freegraphs.J.Combin.Theory Ser.B,162:118–133,2023.4

work page 2023
[45]

Nguyen, A

T. Nguyen, A. Scott, and P. Seymour. A note on the Gyárfás-Sumner conjecture.Graphs Combin., 40(2):Paper No. 33,6,2024.11

work page 2024
[46]

Nguyen, A

T. Nguyen, A. Scott, and P. Seymour. Polynomial bounds for chromatic number VIII. Excluding a path and a com- pletemultipartitegraph.J.GraphTheory,107(3):509–521,2024.6

work page 2024
[47]

T.H.Nguyen.Polynomialχ-boundednessforexcludingP 5.arXiv:2512.24907.1,2,3

work page internal anchor Pith review Pith/arXiv arXiv
[48]

T. H. Nguyen. Highly connected subgraphs with large chromatic number.SIAM J. Discrete Math., 38(1):243–260, 2024.6

work page 2024
[49]

A.Prashant,S.FrancisRaj,andM.Gokulnath.BoundsforthechromaticnumberofsomepK 2-freegraphs.Discrete Appl.Math.,336:99–108,2023.4

work page 2023
[50]

Schiermeyer and B

I. Schiermeyer and B. Randerath. Polynomialχ-binding functions and forbidden induced subgraphs: a survey. GraphsCombin.,35(1):1–31,2019.3

work page 2019
[51]

A. Scott. Graphs of large chromatic number. InICM—International Congress of Mathematicians. Vol. 6. Sections 12–14,pages4660–4680.EMSPress,Berlin,2023.1

work page 2023
[52]

A.ScottandP.Seymour.Inducedsubgraphsofgraphswithlargechromaticnumber.I.Oddholes.J.Combin.Theory Ser.B,121:68–84,2016.2

work page 2016
[53]

A.ScottandP.Seymour.Inducedsubgraphsofgraphswithlargechromaticnumber.IV.Consecutiveholes.J.Com- bin.TheorySer.B,132:180–235,2018.2

work page 2018
[54]

A.ScottandP.Seymour.Asurveyofχ-boundedness.J.GraphTheory,95(3):473–504,2020.1

work page 2020
[55]

A.Scott,P.Seymour,andS.Spirkl.Polynomialboundsforchromaticnumber.I.Excludingabicliqueandaninduced tree.J.GraphTheory,102(3):458–471,2023.11,14

work page 2023
[56]

V.Sivaraman.Someproblemsoninducedsubgraphs.DiscreteAppl.Math.,236:422–427,2018

work page 2018
[57]

D.P.Sumner.Subtreesofagraphandthechromaticnumber.InThetheoryandapplicationsofgraphs(Kalamazoo, Mich.,1980),pages557–576.Wiley,NewYork,1981.4

work page 1980
[58]

D. Wu, J. Li, and R. Li. Improved bounds on the chromatic number of(P3 ∪P 2,W 4)-free graphs.Graphs Combin., 41(5):PaperNo.109,14,2025.4

work page 2025
[59]

C. Zhou, R. Li, J. Song, and D. Wu.χ-binding function for(C 4,t-broom+)-free graphs.Discrete Math., 347(10):114124,2024.4 AppendixA.Brooms InthisappendixwegiveaproofofTheorem2.3. Webeginwith: Lemma A.1.Letq≥1ands≥2beintegers. TheneverygraphGwith χ(G)≥ α(G) s ·q+α(G) s−1 ·R(s,ω(G) +1) contains a stable setIwith|I|=sandχ(G[ T v∈I NG(v)])>q. In particular...

work page 2024