@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",

}