Separating polynomial χ-boundedness from χ-boundedness
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