ALCOMFT-TR-02-105

Josep D\'\iaz, Maria Serna and Dimitrios M. Thilikos
(H,C,K)-coloring: Fast, Easy and Hard cases
Barcelona. Work packages 2 and 4. May 2002.

Abstract: We define a variant of the H-coloring problem by fixing the number of preimages of a subset C of the vertices of H, thus allowing parameterization. We provide sufficient conditions to guarantee that the problem can be solved in O(kn+f(k,H)) steps where f is a function depending only on the number k of fixed preimages and the graph H, and in O(n^k+alpha) steps where alpha is a constant independent of k. Finally, we prove that whenever the non parameterized vertices induce in G a graph that is bipartite and loopless the problem is NP-complete.

Postscript file: ALCOMFT-TR-02-105.ps.gz (158 kb).