a1 Department of Mathematics and Statistics, Arizona State University, Tempe, AZ 85287, USA (e-mail: firstname.lastname@example.org)
a2 Department of Mathematics, University of Illinois, Urbana, IL 61801, USA and Institute of Mathematics, Novosibirsk, 630090, Russia (e-mail: email@example.com)
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)
† 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.