A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
Hal A. Kierstead, Alexandr V. Kostochka · Combinatorics Probability Computing · 2007
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.