TY - JOUR
T1 - List 3-Coloring Graphs with No Induced P6+ rP3
AU - Chudnovsky, Maria
AU - Huang, Shenwei
AU - Spirkl, Sophie
AU - Zhong, Mingxian
N1 - Funding Information:
The first author was supported by NSF Grant DMS-1550991. 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. The second author was supported by the National Natural Science Foundation of China (11801284).
Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2021/1
Y1 - 2021/1
N2 - For an integer t, we let Pt denote the t-vertex path. We write H+ G for the disjoint union of two graphs H and G, and for an integer r and a graph H, we write rH for the disjoint union of r copies of H. We say that a graph G is H-free if no induced subgraph of G is isomorphic to the graph H. In this paper, we study the complexity of k-coloring, for a fixed integer k, when restricted to the class of H-free graphs with a fixed graph H. We provide a polynomial-time algorithm to test if, for fixed r, a (P6+ rP3) -free is three-colorable, and find a coloring if one exists. We also solve the list version of this problem, where each vertex is assigned a list of possible colors, which is a subset of { 1 , 2 , 3 }. This generalizes results of Broersma, Golovach, Paulusma, and Song, and results of Klimošová, Malik, Masařík, Novotná, Paulusma, and Slívová. Our proof uses a result of Ding, Seymour, and Winkler relating matchings and hitting sets in hypergraphs. We also prove that the problem of deciding if a (P5+ P2) -free graph has a k-coloring is NP-hard for every fixed k≥ 5.
AB - For an integer t, we let Pt denote the t-vertex path. We write H+ G for the disjoint union of two graphs H and G, and for an integer r and a graph H, we write rH for the disjoint union of r copies of H. We say that a graph G is H-free if no induced subgraph of G is isomorphic to the graph H. In this paper, we study the complexity of k-coloring, for a fixed integer k, when restricted to the class of H-free graphs with a fixed graph H. We provide a polynomial-time algorithm to test if, for fixed r, a (P6+ rP3) -free is three-colorable, and find a coloring if one exists. We also solve the list version of this problem, where each vertex is assigned a list of possible colors, which is a subset of { 1 , 2 , 3 }. This generalizes results of Broersma, Golovach, Paulusma, and Song, and results of Klimošová, Malik, Masařík, Novotná, Paulusma, and Slívová. Our proof uses a result of Ding, Seymour, and Winkler relating matchings and hitting sets in hypergraphs. We also prove that the problem of deciding if a (P5+ P2) -free graph has a k-coloring is NP-hard for every fixed k≥ 5.
KW - Forbidden induced subgraph
KW - Graph coloring
KW - Polynomial algorithm
UR - http://www.scopus.com/inward/record.url?scp=85088942704&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85088942704&partnerID=8YFLogxK
U2 - 10.1007/s00453-020-00754-y
DO - 10.1007/s00453-020-00754-y
M3 - Article
AN - SCOPUS:85088942704
VL - 83
SP - 216
EP - 251
JO - Algorithmica
JF - Algorithmica
SN - 0178-4617
IS - 1
ER -