Separating polynomial χ-boundedness from χ-boundedness

01/21/2022
by   Marcin Briański, et al.
0

Extending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function fℕ→ℕ we construct a χ-bounded hereditary class of graphs 𝒞 with the property that for every integer n≥ 2 there is a graph in 𝒞 with clique number at most n and chromatic number at least f(n). In particular, this proves that there are hereditary classes of graphs that are χ-bounded but not polynomially χ-bounded.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset