A square-root law for equitable coloring

Abstract

An equitable $k$-coloring of a graph partitions its vertex set into $k$ independent sets whose sizes differ by at most one; the least such $k$ is the equitable chromatic number $\chie(G)$. Every known bound on $\chie$ valid for all graphs, beginning with the Hajnal--Szemerédi theorem, is linear in the maximum degree $\Delta$, and the star $K_{1,\Delta }$, for which $\chie=\ceil{Δ/2}+1$, shows that no general bound below $\Delta /2$ exists. We prove that this obstruction is a shortage of vertices rather than an effect of the degree: every graph with $|V(G)|\ge 3\chi (G)\Delta$ satisfies $\chie(G)=O\bigl(χ(G)^{3/2}\sqrt{Δ/\lnΔ}\bigr)$ throughout the range $\chi (G)\le (\Delta /\ln \Delta {)}^{1/3}$, so that for graphs of large order the degree enters only through $\sqrt{\Delta /\ln \Delta }$, with the chromatic number governing the rest. For each fixed $\ell$, $\ell$-colorable graphs of sufficiently large order satisfy $\chie\le\bigl(2\sqrt2\,\ell\sqrt{\ell-1}+o(1)\bigr)\sqrt{Δ/\lnΔ}$, while a probabilistic construction supplies graphs of arbitrarily large order, bipartite when $\ell =2$, with $\chie\ge\tfrac13\sqrt{(\ell-1)Δ/\lnΔ}$: the order of growth $\Theta \left(\sqrt{\Delta /\ln \Delta }\right)$ is exact for every fixed chromatic number, and the extremal constant is determined up to a factor $O(\chi (G))$. All upper bounds are constructive, and a prescribed-anchor variant of the construction produces equitable colorings of bipartite graphs with $O(\sqrt{\Delta })$ colors in optimal linear time.