On cuts of small chromatic number in sparse graphs

For a given integer k, let ₖ denote the supremum such that every sufficiently large graph G with average degree less than 2 admits a separator X ⊆ V(G) for which $χ(G[X]) < k$. Motivated by the values of ₁, ₂ and ₃, a natural conjecture suggests that ₖ = k for all k. We prove that this conjecture fails dramatically: asymptotically, the trivial lower bound ₖ ≥ k/2 is tight. More precisely, we prove that for every ε>0 and all sufficiently large k, we have ₖ ≤ (1+ε)k/2.