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]

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

  1. ^ 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.
  2. ^ a b 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
  3. ^ 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
  4. ^ Herzberg, Agnes M.; Murty, M. Ram (2007), "Sudoku squares and chromatic polynomials", Notices of the American Mathematical Society, 54 (6): 708–717, MR 2327972
  5. ^ Rosenhouse, Jason; Taalman, Laura (2011), Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle, Oxford University Press, p. 130