Every 4‐Colorable Graph With Maximum Degree 4 Has an Equitable 4‐Coloring

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 K_{r, r} (for odd r) and K_{r + 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