Tag: James Davies

We prove that there is a function $f:\mathbb{N}\to \mathbb{N}$ such that for every function $g:\mathbb{N}\to \mathbb{N}\cup \{\mathrm{\infty }\}$ with $g(1)=1$ and $g\ge f$, there is a hereditary class of graphs $\mathcal{G}$ such that for each $\omega \in \mathbb{N}$, the maximum chromatic number of a graph in $\mathcal{G}$ with clique number $\omega$ is equal to $g(\omega )$. This extends a recent breakthrough of Carbonero, Hompe, Moore, and Spirk. In particular, this proves that there are hereditary classes of graphs that are $\chi$-bounded but not polynomially $\chi$-bounded.

Joint work with Marcin Briański and Bartosz Walczak.