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

1 Scopus citations

Abstract

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
DOIs
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
Volume144
ISSN (Print)1868-8969

Conference

Conference27th Annual European Symposium on Algorithms, ESA 2019
CountryGermany
CityMunich/Garching
Period9/9/199/11/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

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

Fingerprint Dive into the research topics of 'Complexity of C<sub>K</sub>-coloring in hereditary classes of graphs'. Together they form a unique fingerprint.

  • Cite this

    Chudnovsky, M., Huang, S., Rzążewski, P., Spirkl, S., & Zhong, M. (2019). Complexity of CK-coloring in hereditary classes of graphs. In M. A. Bender, O. Svensson, & G. Herman (Eds.), 27th Annual European Symposium on Algorithms, ESA 2019 [31] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 144). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2019.31