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:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)