Premium
Every 4‐Colorable Graph With Maximum Degree 4 Has an Equitable 4‐Coloring
Author(s) -
Kierstead H. A.,
Kostochka A. V.
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20630
Subject(s) - combinatorics , mathematics , conjecture , chen , degree (music) , graph , discrete mathematics , list coloring , graph theory , graph power , line graph , physics , paleontology , acoustics , biology
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