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\'edi theorem, is linear in the maximum degree $\Delta$, and the star $K_{1,\Delta}$, for which $\chie=\ceil{\Delta/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)|\ge3\chi(G)\Delta$ satisfies $\chie(G)=O\bigl(\chi(G)^{3/2}\sqrt{\Delta/\ln\Delta}\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{\Delta/\ln\Delta}$, while a probabilistic construction supplies graphs of arbitrarily large order, bipartite when $\ell=2$, with $\chie\ge\tfrac13\sqrt{(\ell-1)\Delta/\ln\Delta}$: the order of growth $\Theta\bigl(\sqrt{\Delta/\ln\Delta}\bigr)$ 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.