The Ramsey-type bound conjecture for multipartite-free chi-bounded classes
The Ramsey-type bound conjecture for multipartite-free chi-bounded classes
Let be a -bounded graph class. For integers , let be the disjoint union of copies of , and let be its complement. Let denote the least integer such that every -vertex graph has a stable set of size or a clique of size .
Ramsey-type bound conjecture. For every -bounded class and every two integers , there exists such that every -free graph satisfies
For -dense classes, a bound of this form follows from the density framework, whereas its asserted extension to all -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
Sign in to submit a solution.
No solutions have been posted yet.