The cocktail-party-free subclass conjecture for chi-bounded graph classes
The cocktail-party-free subclass conjecture for chi-bounded graph classes
For an integer , let be the disjoint union of copies of , and let be its complement. A graph class is linearly -bounded if there is a constant such that every graph in the class satisfies .
Cocktail-party-free subclass conjecture. For every integer , the -free subclass of every -bounded class is linearly -bounded.
This extends the preceding -free subclass conjecture and is known for subclasses of -dense classes, but remains open for all -bounded classes.
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.