@inproceedings{ce50c57fb81f4eb0b42a3689d323d445,
title = "(H,C,K)-coloring: Fast, easy, and hard cases",
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(nk+c) steps where c 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.",
author = "Josep D{\'i}az and Maria Serna and Thilikos, {Dimitrios M.}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 26th International Symposium on Mathematical Foundations of Computer Science, MFCS 2001 ; Conference date: 27-08-2001 Through 31-08-2001",
year = "2001",
doi = "10.1007/3-540-44683-4_27",
language = "English (US)",
isbn = "9783540446835",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "304--315",
editor = "Jiri Sgall and Ales Pultr and Petr Kolman",
booktitle = "Mathematical Foundations of Computer Science 2001 - 26th International Symposium, MFCS 2001, Proceedings",
}