On cuts of small chromatic number in sparse graphs
Guillaume Aubian, Marthe Bonamy, Romain Bourneuf, Oscar Fontaine, Lucas Picasarri‐Arrieta · arXiv (Cornell University) · 2025
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 $χ(G[X]) 0$ and all sufficiently large $k$, we have $\ell_k \leq (1+\varepsilon)\tfrac{k}{2}$.