precoloring extension
In graph theory, precoloring extension is the problem of extending a graph coloring of a subset of the vertices of a graph, with a given set of colors, to a coloring of the whole graph that does not assign the same color to any two adjacent vertices.
Complexity
Precoloring extension has the usual graph coloring problem as a special case, in which the initially colored subset of vertices is empty; therefore, it is NP-complete.
However, it is also NP-complete for some other classes of graphs on which the usual graph coloring problem is easier. For instance it is NP-complete on the rook's graphs, for which it corresponds to the problem of completing a partially filled-in Latin square.{{citation
| last = Colbourn | first = Charles J.
| doi = 10.1016/0166-218X(84)90075-1
| issue = 1
| journal = Discrete Applied Mathematics
| mr = 739595
| pages = 25–30
| title = The complexity of completing partial Latin squares
| volume = 8
| year = 1984| doi-access = free
}}.
The problem may be solved in polynomial time for graphs of bounded treewidth, but the exponent of the polynomial depends on the treewidth.{{citation
| last1 = Jansen | first1 = Klaus
| last2 = Scheffler | first2 = Petra
| doi = 10.1016/S0166-218X(96)00085-6
| issue = 2
| journal = Discrete Applied Mathematics
| mr = 1451958
| pages = 135–155
| title = Generalized coloring for tree-like graphs
| volume = 75
| year = 1997| doi-access = free
| last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows
| last2 = Fomin | first2 = Fedor V.
| last3 = Lokshtanov | first3 = Daniel
| last4 = Rosamond | first4 = Frances | author4-link = Frances A. Rosamond
| last5 = Saurabh | first5 = Saket
| last6 = Szeider | first6 = Stefan
| last7 = Thomassen | first7 = Carsten | author7-link = Carsten Thomassen (mathematician)
| doi = 10.1016/j.ic.2010.11.026
| issue = 2
| journal = Information and Computation
| mr = 2790022
| pages = 143–153
| title = On the complexity of some colorful problems parameterized by treewidth
| volume = 209
| year = 2011| url = https://backend.orbit.dtu.dk/ws/files/5275033/195.Fellows%20et%20al.pdf }}
It may be solved in linear time for precoloring extension instances in which both the number of colors and the treewidth are bounded.
Related problems
Precoloring extension may be seen as a special case of list coloring, the problem of coloring a graph in which no vertices have been colored, but each vertex has an assigned list of available colors.
To transform a precoloring extension problem into a list coloring problem, assign each uncolored vertex in the precoloring extension problem a list of the colors not yet used by its initially-colored neighbors,
and then remove the colored vertices from the graph.
Sudoku puzzles may be modeled mathematically as instances of the precoloring extension problem on Sudoku graphs.{{citation
| last1 = Herzberg | first1 = Agnes M. | author1-link = Agnes M. Herzberg
| last2 = Murty | first2 = M. Ram | author2-link = M. Ram Murty
| issue = 6
| journal = Notices of the American Mathematical Society
| mr = 2327972
| pages = 708–717
| title = Sudoku squares and chromatic polynomials
| volume = 54
| year = 2007}}{{citation
| last1 = Rosenhouse | first1 = Jason | author1-link = Jason Rosenhouse
| last2 = Taalman | first2 = Laura | author2-link = Laura Taalman
| page = 130
| publisher = Oxford University Press
| title = Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle
| title-link = Taking Sudoku Seriously
| year = 2011}}
References
{{reflist}}
External links
- [http://www.cs.bme.hu/~dmarx/prext.php Bibliography on precoloring extension], Dániel Marx