TY - GEN
T1 - Complexity of CK-coloring in hereditary classes of graphs
AU - Chudnovsky, Maria
AU - Huang, Shenwei
AU - Rzążewski, Paweł
AU - Spirkl, Sophie
AU - Zhong, Mingxian
N1 - Funding Information:
Maria Chudnovsky: Supported by NSF grant DMS-1763817. This material is based upon work supported in part by the U. S. Army Research Laboratory and the U. S. Army Research Office under grant number W911NF-16-1-0404. Shenwei Huang: This research is supported by the National Natural Science Foundation of China (11801284). Sophie Spirkl: This material is based upon work supported by the National Science Foundation under Award No. DMS1802201. We are grateful to anonymous reviewers for their comments that helped improve the presentation of the paper.
Publisher Copyright:
© Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski, Sophie Spirkl, and Mingxian Zhong.
PY - 2019/9
Y1 - 2019/9
N2 - 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.
AB - 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.
KW - Computational complexity
KW - Forbidden induced subgraph
KW - Hereditary class
KW - Homomorphism
UR - http://www.scopus.com/inward/record.url?scp=85074812929&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85074812929&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2019.31
DO - 10.4230/LIPIcs.ESA.2019.31
M3 - Conference contribution
AN - SCOPUS:85074812929
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 27th Annual European Symposium on Algorithms, ESA 2019
A2 - Bender, Michael A.
A2 - Svensson, Ola
A2 - Herman, Grzegorz
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 27th Annual European Symposium on Algorithms, ESA 2019
Y2 - 9 September 2019 through 11 September 2019
ER -