On equitable coloring of d-degenerate graphs

A. V. Kostochka, K. Nakprasit, S. V. Pemmaraju

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. A d-degenerate graph is a graph G in which every subgraph has a vertex with degree at most d. A star S m with m rays is an example of a 1-degenerate graph with maximum degree m that needs at least 1 + m/2 colors for an equitable coloring. Our main result is that every n-vertex d-degenerate graph G with maximum degree at most n/15 can be equitably k-colored for each k ≥ 16d. The proof of this bound is constructive. We extend the algorithm implied in the proof to an O(d)-factor approximation algorithm for equitable coloring of an arbitrary d-degenerate graph. Among the implications of this result is an O(1)-factor approximation algorithm for equitable coloring of planar graphs with fewest colors. A variation of equitable coloring (equitable partitions) is also discussed.

Original languageEnglish (US)
Pages (from-to)83-95
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Issue number1
StatePublished - 2005


  • Equitable coloring
  • Graph coloring
  • d-degenerate graphs

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'On equitable coloring of d-degenerate graphs'. Together they form a unique fingerprint.

Cite this