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.
Read more about this topic: Equitable Coloring
Famous quotes containing the word complexity:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)