Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 82-91 |
Number of pages | 10 |
Journal | Theoretical Computer Science |
Volume | 349 |
Issue number | 1 |
DOIs | |
State | Published - Dec 12 2005 |
Keywords
- Average degree
- Brooks' Theorem
- Equitable coloring
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)