Separating polynomial $\chi$-boundedness from $\chi$-boundedness

Abstract

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

v2: new proof with improved results

References in corpus (1)

• Separating polynomial $\chi$-boundedness from $\chi$-boundedness

Cited by in corpus (2)

• Separating polynomial $\chi$-boundedness from $\chi$-boundedness
• Reuniting $\chi$-boundedness with polynomial $\chi$-boundedness