Equitable Coloring - Computational Complexity

Computational Complexity

The problem of finding equitable colorings with as few colorings as possible (below the Hajnal-Szemerédi bound) has also been studied. A straightforward reduction from graph coloring to equitable coloring may be proven by adding sufficiently many isolated vertices to a graph, showing that it is NP-complete to test whether a graph has an equitable coloring with a given number of colors (greater than two). 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. However, Fellows et al. (2007) prove that, when the treewidth is a parameter to the algorithm, the problem is W-hard. Thus, it is unlikely that there exists a polynomial time algorithm independent of this parameter, or even that the dependence on the parameter may be moved out of the exponent in the formula for the running time.