Separating Polynomial χ-Boundedness from χ-Boundedness

Abstract

Extending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function f:N→N∪{∞}$$f:\mathbb {N}\rightarrow \mathbb {N}\cup {\infty }$$ with f(1)=1$$f(1)=1$$ and f(n)⩾3n+13$$f(n)\geqslant \left( {\begin{array}{c}3n+1\ 3\end{array}}\right) $$, we construct a hereditary class of graphs G$${\mathcal {G}}$$ such that the maximum chromatic number of a graph in G$${\mathcal {G}}$$ with clique number n is equal to f(n) for every n∈N$$n\in \mathbb {N}$$. In particular, we prove that there exist hereditary classes of graphs that are χ$$\chi $$-bounded but not polynomially χ$$\chi $$-bounded.