TY - JOUR
T1 - On equitable Δ-coloring of graphs with low average degree
AU - Kostochka, A. V.
AU - Nakprasit, K.
N1 - This work was partially supported by the NSF Grants DMS-0099608 and DMS-0400498. ∗ Corresponding author. Department of Mathematics, The University of Illinois, Urbana, IL 61801, USA. E-mail addresses: [email protected] (A.V. Kostochka), [email protected] (K. Nakprasit).
PY - 2005/12/12
Y1 - 2005/12/12
N2 - 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 Szemerédi proved that every graph with maximum degree Δ is equitably k-colorable for every k≥Δ+1. Chen, Lih, and Wu conjectured that every connected graph with maximum degree Δ≥3 distinct from KΔ+1 and KΔ,Δ is equitably Δ-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 Δ/5.
AB - 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 Szemerédi proved that every graph with maximum degree Δ is equitably k-colorable for every k≥Δ+1. Chen, Lih, and Wu conjectured that every connected graph with maximum degree Δ≥3 distinct from KΔ+1 and KΔ,Δ is equitably Δ-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 Δ/5.
KW - Average degree
KW - Brooks' Theorem
KW - Equitable coloring
UR - http://www.scopus.com/inward/record.url?scp=27844527527&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=27844527527&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2005.09.031
DO - 10.1016/j.tcs.2005.09.031
M3 - Article
AN - SCOPUS:27844527527
SN - 0304-3975
VL - 349
SP - 82
EP - 91
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1
ER -