ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. 62,   2   (1993)
pp.   139-153

PRECOLORING EXTENSION WITH FIXED COLOR BOUND
J. KRATOCHVIL

Abstract.  Precoloring Extension (shortly PrExt) is the following problem: Given a graph \$G\$ with some \pd vertices and a color bound \$k\$, can the \PI of \$G\$ be extended to a proper coloring of all vertices of \$G\$ using not more than \$k\$ colors? Answering an open problem from Ref. 6, we prove that PrExt with fixed color bound \$k=3\$ is \np 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).

AMS subject classification
Keywords