On equitable Δ-coloring of graphs with low average degree

A. V. Kostochka, K. Nakprasit

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)82-91
Number of pages10
JournalTheoretical Computer Science
Issue number1
StatePublished - Dec 12 2005


  • Average degree
  • Brooks' Theorem
  • Equitable coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On equitable Δ-coloring of graphs with low average degree'. Together they form a unique fingerprint.

Cite this