Resolving a problem raised by Norin, we show that for each $k in mathbb{N}$, there exists an $f(k) le 7k$ such that every graph $G$ with chromatic number at least $f(k)+1$ contains a subgraph $H$ with both connectivity and chromatic number at least $k$. This result is best-possible up to multiplicative constants, and sharpens earlier results of Alon-Kleitman-Thomassen-Saks-Seymour from 1987 showing that $f(k) = O(k^3)$, and of Chudnovsky-Penev-Scott-Trotignon from 2013 showing that $f(k) = O(k^2)$. Our methods are robust enough to handle list colouring as well: we also show that for each $k in mathbb{N}$, there exists an $f_ell(k) le 4k$ such that every graph $G$ with list chromatic number at least $f_ell(k)+1$ contains a subgraph $H$ with both connectivity and list chromatic number at least $k$. This result is again best-possible up to multiplicative constants; here, unlike with $f(cdot)$, even the existence of $f_ell(cdot)$ appears to have been previously unknown.
Download