Complexity of CK-coloring in hereditary classes of graphs

Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski, Sophie Spirkl, Mingxian Zhong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


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.

Original languageEnglish (US)
Title of host publication27th Annual European Symposium on Algorithms, ESA 2019
EditorsMichael A. Bender, Ola Svensson, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771245
StatePublished - Sep 2019
Event27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany
Duration: Sep 9 2019Sep 11 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference27th Annual European Symposium on Algorithms, ESA 2019

All Science Journal Classification (ASJC) codes

  • Software


  • Computational complexity
  • Forbidden induced subgraph
  • Hereditary class
  • Homomorphism


Dive into the research topics of 'Complexity of CK-coloring in hereditary classes of graphs'. Together they form a unique fingerprint.

Cite this