Equitable coloring

The case Δ = 2 is straightforward (any union of paths and cycles may be equitably colored by using a repeated pattern of three colors, with minor adjustments to the repetition when closing a cycle) and the case Δ + 1= n/3 had previously been solved by Corrádi & Hajnal (1963).

A polynomial time algorithm for finding equitable colorings with this many colors was described by Kierstead and Kostochka; they credit Marcelo Mydlarz and Endre Szemerédi with a prior unpublished polynomial time algorithm.

Kierstead and Kostochka also announce but do not prove a strengthening of the theorem, to show that an equitable k+1-coloring exists whenever every two adjacent vertices have degrees adding to at most 2k + 1.

A strengthened version of the conjecture states that each such graph has an equitable coloring with exactly Δ colors, with one additional exception, a complete bipartite graph in which both sides of the bipartition have the same odd number of vertices.

For any tree with maximum degree Δ, the equitable chromatic number is at most with the worst case occurring for a star.

However, the problem becomes more interesting when restricted to special classes of graphs or from the point of view of parameterized complexity.

Bodlaender & Fomin (2005) showed that, given a graph G and a number c of colors, it is possible to test whether G admits an equitable c-coloring in time O(nO(t)), where t is the treewidth of G; in particular, equitable coloring may be solved optimally in polynomial time for trees (previously known due to Chen & Lih 1994) and outerplanar graphs.

A polynomial time algorithm is also known for equitable coloring of split graphs.

One motivation for equitable coloring suggested by Meyer (1973) concerns scheduling problems.

The Hajnal-Szemerédi theorem has also been used to bound the variance of sums of random variables with limited dependence (Pemmaraju 2001; Janson & Ruciński 2002).

If (as in the setup for the Lovász local lemma) each variable depends on at most Δ others, an equitable coloring of the dependence graph may be used to partition the variables into independent subsets within which Chernoff bounds may be calculated, resulting in tighter overall bounds on the variance than if the partition were performed in a non-equitable way.