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.[1]
The problem may be solved in polynomial time for graphs of bounded treewidth, but the exponent of the polynomial depends on the treewidth.[2][3] It may be solved in linear time for precoloring extension instances in which both the number of colors and the treewidth are bounded.[2]
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.[4][5]
References
- ↑ Colbourn, Charles J. (1984), "The complexity of completing partial Latin squares", Discrete Applied Mathematics 8 (1): 25–30, doi:10.1016/0166-218X(84)90075-1.
- ↑ 2.0 2.1 Jansen, Klaus; Scheffler, Petra (1997), "Generalized coloring for tree-like graphs", Discrete Applied Mathematics 75 (2): 135–155, doi:10.1016/S0166-218X(96)00085-6
- ↑ "On the complexity of some colorful problems parameterized by treewidth", Information and Computation 209 (2): 143–153, 2011, doi:10.1016/j.ic.2010.11.026
- ↑ "Sudoku squares and chromatic polynomials", Notices of the American Mathematical Society 54 (6): 708–717, 2007
- ↑ Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle, Oxford University Press, 2011, p. 130
External links
- Bibliography on precoloring extension, Dániel Marx
 |  |
