ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

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.

Download: Adobe PDF

Compressed Postscript

Acta Mathematica Universitatis Comenianae
Institute of Applied Mathematics
Faculty of Mathematics, Physics and Informatics
Comenius University
842 48 Bratislava, Slovak Republic
Telephone: + 421-2-60295111 Fax: + 421-2-65425882
e-Mail: amuc@fmph.uniba.sk Internet: www.iam.fmph.uniba.sk/amuc