Every 4‐Colorable Graph With Maximum Degree 4 Has an Equitable 4‐Coloring
Hal A. Kierstead, Alexandr V. Kostochka · Journal of Graph Theory · 2011
Abstract Chen et al., conjectured that for r≥3, the only connected graphs with maximum degree at most r that are not equitably r‐colorable are Kr, r (for odd r) and Kr + 1. If true, this would be a joint strengthening of the Hajnal–Szemerédi theorem and Brooks' theorem. Chen et al., proved that their conjecture holds for r = 3. In this article we study properties of the hypothetical minimum counter‐examples to this conjecture and the structure of “optimal” colorings of such graphs. Using these properties and structure, we show that the Chen–Lih–Wu Conjecture holds for r≤4. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:31–48, 2012