Complexity of Ck-coloring in hereditary classes of graphs

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

Research output: Contribution to journalArticlepeer-review


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 list variant, can be solved in polynomial time in P9-free graphs. The algorithm extends to the list version of Ck-COLORING, where k≥10 is an even number. On the other hand, we prove that if some component of F is not a subgraph of a subdivided claw, then the following problems are NP-complete in F-free graphs: 1. the precoloring extension version of Ck-COLORING for every odd k≥5; 2. the list version of Ck-COLORING for every even k≥6.

Original languageEnglish (US)
Article number105015
JournalInformation and Computation
StatePublished - Jun 2023

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


  • Computational complexity
  • Graph coloring
  • Hereditary graph classes
  • Homomorphism


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

Cite this