Top Qs
Timeline
Chat
Perspective

Precoloring extension

From Wikipedia, the free encyclopedia

Remove ads

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]

Remove ads

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]

Remove ads

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads