Polynomial χ-boundedness conjecture for bounded merge-width classes
Polynomial χ-boundedness conjecture for bounded merge-width classes
A graph class is χ-bounded if there is a function such that every graph in the class satisfies , where is the chromatic number and is the clique number. It is polynomially χ-bounded if can be chosen to be a polynomial. Polynomial χ-boundedness conjecture for bounded merge-width classes. Every class of graphs with bounded merge-width is polynomially χ-bounded. Bounded merge-width classes are already known to be χ-bounded, and the conjecture asks for the stronger polynomial dependence on clique number. The stated paper proves χ-boundedness, but does not establish this polynomial strengthening.
Sources & referencesView supporting material
Primary source
Marthe Bonamy and Colin Geniet, “χ-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs”, arXiv:2504.08266 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.