Precoloring extension with fixed color bound.
Jan Kratochvı́l · 1993
. Precoloring Extension (shortly PrExt) is the following problem: Given a graph G with some precolored vertices and a color bound k, can the precoloring of G be extended to a proper coloring of all vertices of G using not more than k colors? Answering an open problem from [6], we prove that PrExt with fixed color bound k = 3 is NP-complete for bipartite (and even planar) graphs, and we prove a general result on parametrized PrExt. We also give a simplified argument why PrExt with fixed color bound is solvable in polynomial time for graphs of bounded treewidth (and hence also for chordal graphs). 1. Introduction and Statement of the Results All graphs considered are finite, undirected and without loops or multiple edges. A coloring of a graph is any mapping from its vertex set into a set of colors, a coloring is proper if adjacent vertices are mapped onto distinct colors. The following decision problem is introduced in [1] and studied in [6, 7, 8]: Precoloring Extension (short...