The C4-free subclass conjecture for chi-bounded graph classes
The C4-free subclass conjecture for chi-bounded graph classes
Let be a class of graphs. Its -free subclass consists of the graphs in with no induced cycle on four vertices. A graph class is linearly -bounded if there is a constant such that every graph in the class satisfies .
C4-free subclass conjecture. The -free subclass of every -bounded class is linearly -bounded.
This would generalize known results for several -free subclasses, while the statement remains open for arbitrary -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.