On cuts of small chromatic number in sparse graphs

Abstract

For a given integer $k$, let ${\ell }_k$ denote the supremum $\ell$ such that every sufficiently large graph $G$ with average degree less than $2\ell$ admits a separator $X\subseteq V(G)$ for which $\chi (G[X])<k$. Motivated by the values of ${\ell }_1$, ${\ell }_2$ and ${\ell }_3$, a natural conjecture suggests that ${\ell }_k=k$ for all $k$. We prove that this conjecture fails dramatically: asymptotically, the trivial lower bound ${\ell }_k\ge \frac{k}{2}$ is tight. More precisely, we prove that for every $\epsilon >0$ and all sufficiently large $k$, we have ${\ell }_k\le (1+\epsilon )\frac{k}{2}$.