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
[edit]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
[edit]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
[edit]- ↑ 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, MR 0739595.
- 1 2 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, MR 1451958
- ↑ Fellows, Michael R.; Fomin, Fedor V.; Lokshtanov, Daniel; Rosamond, Frances; Saurabh, Saket; Szeider, Stefan; Thomassen, Carsten (2011), "On the complexity of some colorful problems parameterized by treewidth" (PDF), Information and Computation, 209 (2): 143–153, doi:10.1016/j.ic.2010.11.026, MR 2790022
- ↑ Herzberg, Agnes M.; Murty, M. Ram (2007), "Sudoku squares and chromatic polynomials", Notices of the American Mathematical Society, 54 (6): 708–717, MR 2327972
- ↑ Rosenhouse, Jason; Taalman, Laura (2011), Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle, Oxford University Press, p. 130
External links
[edit]- Bibliography on precoloring extension, Dániel Marx