A fast algorithm for equitable coloring

Henry A. Kierstead, Alexandr V. Kostochka, Marcelo Mydlarz, Endre Szemerédi

Research output: Contribution to journalArticlepeer-review

Abstract

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most one. The celebrated Hajnal-Szemerédi Theorem states: For every positive integer r, every graph with maximum degree at most r has an equitable coloring with r+1 colors. We show that this coloring can be obtained in O(rn2) time, where n is the number of vertices.

Original languageEnglish (US)
Pages (from-to)217-224
Number of pages8
JournalCombinatorica
Volume30
Issue number2
DOIs
StatePublished - 2010

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'A fast algorithm for equitable coloring'. Together they form a unique fingerprint.

Cite this