TY - JOUR

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:
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.Supported by the National Natural Science Foundation of China (12171256).Supported by Polish National Science Centre grant no. 2018/31/D/ST6/00062.This material is based upon work supported by the National Science Foundation under Award No. DMS-1802201. Current address: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L3G1.
Publisher Copyright:
© 2023 Elsevier Inc.

PY - 2023/6

Y1 - 2023/6

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 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.

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 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.

KW - Computational complexity

KW - Graph coloring

KW - Hereditary graph classes

KW - Homomorphism

UR - http://www.scopus.com/inward/record.url?scp=85152065160&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85152065160&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2023.105015

DO - 10.1016/j.ic.2023.105015

M3 - Article

AN - SCOPUS:85152065160

SN - 0890-5401

VL - 292

JO - Information and Computation

JF - Information and Computation

M1 - 105015

ER -