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 one. \textit{B.-L. Chen, K.-W. Lih}, and \textit{P.-L. Wu} [Eur. J. Comb. 15, 443--447 (1994; Zbl 0809.05050)] proposed the following conjecture. Any connected graph with maximum degree \(\Delta \geq 3\) distinct from \(K_{\Delta+1}\) and \(K_{\Delta, \Delta}\) has an equitable coloring using \(\Delta\) colors. In this paper, this conjecture is established for graphs with average degree at most \(\Delta/5\).
scientific article; zbMATH DE number 5013296