On cuts of small chromatic number in sparse graphs

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