A fast algorithm for equitable coloring (Q532129)

An equitable \(k\)-colouring of a graph is a proper vertex colouring with \(k\) colors, in which the sizes of any two colour classes differ by at most one. It was conjectured by P. Erdős and proved by \textit{A. Hajnal} and \textit{E. Szemerédi} [Combinat. Theory Appl., Colloquia Math. Soc. János Bolyai 4, 601--623 (1970; Zbl 0217.02601)] that every graph with maximum degree at most \(r\) admits an equitable \((r+1)\)-colouring. The authors present a less complicated and shorter proof of this celebrated Hajnal-Szemerédi theorem by using new methods and recombining old ideas. Their proof yields, moreover, a simple \(O(rn^2)\) time algorithm for obtaining an equitable \((r+1)\)-colouring, where \(n\) is the vertex number of the given graph with maximum degree at most \(r\). This algorithm is faster than those obtained previously in [\textit{H. A. Kierstead} and \textit{A. V. Kostochka}, Comb. Probab. Comput. 17, No.~2, 265--270 (2008; Zbl 1163.05015); \textit{M. Mydlarz and E. Szemerédi}, Algorithmic Brooks' theorem, manuscript]. \textit{H. A. Kierstead} and \textit{A. V. Kostochka} [J. Comb. Theory, Ser. B 98, No.~1, 226--234 (2008; Zbl 1127.05039)] improved the Hajnal-Szemerédi theorem by showing that any graph, in which the degree sum of any two adjacent vertices is at most \(2r+1\), has an equitable \((r+1)\)-colouring. The authors conjecture that such a colouring can be constructed by a polynomial time algorithm.