@inproceedings{17c3b9d4740a4fa19e643710d0a3dea7,

title = "Complexity of CK-coloring in hereditary classes of graphs",

abstract = "For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f : V (G) → V (H) such that for every edge uv ∈ E(G) it holds that f(u)f(v) ∈ E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of Pt-free graphs. We show that for every odd k ≥ 5 the Ck-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P9-free graphs. On the other hand, we prove that the extension version of Ck-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw.",

keywords = "Computational complexity, Forbidden induced subgraph, Hereditary class, Homomorphism",

author = "Maria Chudnovsky and Shenwei Huang and Pawe{\l} Rz{\c a}{\.z}ewski and Sophie Spirkl and Mingxian Zhong",

year = "2019",

month = sep,

doi = "10.4230/LIPIcs.ESA.2019.31",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Bender, {Michael A.} and Ola Svensson and Grzegorz Herman",

booktitle = "27th Annual European Symposium on Algorithms, ESA 2019",

address = "Germany",

note = "27th Annual European Symposium on Algorithms, ESA 2019 ; Conference date: 09-09-2019 Through 11-09-2019",

}