On equitable Δ-coloring of graphs with low average degree

A. V. Kostochka, K. Nakprasit

Research output: Contribution to journalArticlepeer-review

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

Keywords

  • Average degree
  • Brooks' Theorem
  • Equitable coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this