Separating polynomial χ-boundedness from χ-boundedness

01/21/2022

∙

by   Marcin Briański, et al.

∙

0

∙

share

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.