Combinatorics, Probability and Computing

Table of Contents - 2008 - Volume 17, Issue 02  

Paper

A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring

H. A. KIERSTEADa1† and A. V. KOSTOCHKAa2‡

a1 Department of Mathematics and Statistics, Arizona State University, Tempe, AZ 85287, USA (e-mail: kierstead@asu.edu)

a2 Department of Mathematics, University of Illinois, Urbana, IL 61801, USA and Institute of Mathematics, Novosibirsk, 630090, Russia (e-mail: kostochk@math.uiuc.edu)

Abstract

A proper vertex colouring of a graph is equitable if the sizes of colour classes differ by at most one. We present a new shorter proof of the celebrated Hajnal–Szemerédi theorem: for every positive integer r, every graph with maximum degree at most r has an equitable colouring with r+1 colours. The proof yields a polynomial time algorithm for such colourings.

(Received August 07 2006)

(Revised March 28 2007)

Footnotes

† Research of this author is supported in part by NSA grant MDA 904-03-1-0007.

‡ Research of this author is supported in part by NSF grants DMS-0400498 and DMS-0650784, and by grant 05-01-00816 of the Russian Foundation for Basic Research.