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