On equitable Delta-coloring of graphs with low average degree
An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most 1. Hajnal and Szemeredi proved that every graph with maximum degree Delta is equitably k-colorable for every k >= Delta + 1. Chen, Lih, and Wu conjectured that every connected graph with maximum degree Delta >= 3 distinct from KDelta+1 and K-Delta,K-Delta is equitably Delta-colorable. This conjecture has been proved for graphs in some classes such as bipartite graphs, outerplanar graphs, graphs with maximum degree 3, interval graphs. We prove that this conjecture holds for graphs with average degree at most Delta/5. (c) 2005 Elsevier B.V. All rights reserved.
average degree equitable coloring brooks'theorem