2026-08-10T17:28:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11152 2024-03-06T10:47:34Z ddc:004 open_access

Complexity of C_k-Coloring in Hereditary Classes of Graphs Chudnovsky, Maria Huang, Shenwei Rzążewski, Paweł Spirkl, Sophie Zhong, Mingxian homomorphism hereditary class computational complexity forbidden induced subgraph 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 in E(G) it holds that f(u)f(v)in 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 P_t-free graphs. We show that for every odd k >= 5 the C_k-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P_9-free graphs. On the other hand, we prove that the extension version of C_k-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maria Chudnovsky and Shenwei Huang and Paweł Rzążewski and Sophie Spirkl and Mingxian Zhong 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.31 urn:nbn:de:0030-drops-111529 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.31 eng https://creativecommons.org/licenses/by/3.0/legalcode