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 -