Show simple item record

dc.contributor.authorChudnovsky, Maria
dc.contributor.authorHuang, Shenwei
dc.contributor.authorRzazewski, Pawel
dc.contributor.authorSpirkl, Sophie
dc.contributor.authorZhong, Mingxian
dc.date.accessioned2023-03-31 19:27:26 (GMT)
dc.date.available2023-03-31 19:27:26 (GMT)
dc.date.issued2023-06
dc.identifier.urihttps://doi.org/10.1016/j.ic.2023.105015
dc.identifier.urihttp://hdl.handle.net/10012/19243
dc.description.abstractFor 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: a) the precoloring extension version of Ck-Coloring for every odd k ≥ 5; b) the list version of Ck-Coloring for every even k ≥ 6.en
dc.description.sponsorshipNSF, grant DMS-1763817 || U.S. Army Research Laboratory and the U.S. Army Research Office, Grant W911NF-16-1-0404 || National Natural Science Foundation of China, 12171256 || Polish National Science Centre, Grant 2018/31/D/ST6/00062 || National Science Foundation, DMS-1802201.en
dc.language.isoenen
dc.publisherElsevieren
dc.relation.ispartofseriesInformation and Computation;105015
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 International*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectgraph coloringen
dc.subjecthomomorphismen
dc.subjectcomputational complexityen
dc.subjecthereditary graph classesen
dc.titleComplexity of Ck-coloring in hereditary classes of graphsen
dc.typeArticleen
dcterms.bibliographicCitationChudnovsky, M., Huang, S., Rzążewski, P., Spirkl, S., & Zhong, M. (2023). Complexity of C-coloring in hereditary classes of graphs. Information and Computation, 292, 105015. https://doi.org/10.1016/j.ic.2023.105015en
uws.contributor.affiliation1Faculty of Mathematicsen
uws.contributor.affiliation2Combinatorics and Optimizationen
uws.typeOfResourceTexten
uws.peerReviewStatusRevieweden
uws.scholarLevelFacultyen


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 International
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivatives 4.0 International

UWSpace

University of Waterloo Library
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
519 888 4883

All items in UWSpace are protected by copyright, with all rights reserved.

DSpace software

Service outages