Polynomial χ-boundedness conjecture for bounded merge-width classes

A graph class is χ-bounded if there is a function ff such that every graph GG in the class satisfies χ(G)f(ω(G))\chi(G)\leq f(\omega(G)), where χ(G)\chi(G) is the chromatic number and ω(G)\omega(G) is the clique number. It is polynomially χ-bounded if ff 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

Never refreshed

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

Solutions 0

No solutions have been posted yet.