The Ramsey-type bound conjecture for multipartite-free chi-bounded classes

From papers

Let G\mathcal G be a χ\chi-bounded graph class. For integers m,s1m,s\ge1, let mKsmK_s be the disjoint union of mm copies of KsK_s, and let mKs\overline{mK_s} be its complement. Let R(s,w)R(s,w) denote the least integer n1n\ge1 such that every nn-vertex graph has a stable set of size ss or a clique of size ww.

Ramsey-type bound conjecture. For every χ\chi-bounded class G\mathcal G and every two integers m,s1m,s\ge1, there exists C=C(G,m,s)1C=C(\mathcal G,m,s)\ge1 such that every mKs\overline{mK_s}-free graph GGG\in\mathcal G satisfies

χ(G)CR(s,ω(G)+1).\chi(G)\le C\cdot R(s,\omega(G)+1).

For χ\chi-dense classes, a bound of this form follows from the density framework, whereas its asserted extension to all χ\chi-bounded classes remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Tung Nguyen and Sang-il Oum, “Ramsey-type χ-bounds for χ-bounded graph classes”, arXiv:2605.08848 (2026).

Solutions 0

No solutions have been posted yet.