In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, precoloring extension is the problem of extending a
graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
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.
The problem may be solved in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
for graphs of bounded
treewidth, but the exponent of the polynomial depends on the treewidth.
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 In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing
and by Erdős, Rubin, and Taylor ...
, 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 graph
In the mathematics of Sudoku, the Sudoku graph is an undirected graph whose vertices represent the cells of a (blank) Sudoku puzzle and whose edges represent pairs of cells that belong to the same row, column, or block of the puzzle. The problem ...
s.
References
{{reflist
External links
Bibliography on precoloring extension
Dániel Marx
Graph coloring