dc.contributor.author | Chudnovsky, Maria | |
dc.contributor.author | Huang, Shenwei | |
dc.contributor.author | Spirkl, Sophie | |
dc.contributor.author | Zhong, Mingxian | |
dc.date.accessioned | 2022-08-12 00:05:51 (GMT) | |
dc.date.available | 2022-08-12 00:05:51 (GMT) | |
dc.date.issued | 2021-01-01 | |
dc.identifier.uri | https://doi.org/10.1007/s00453-020-00754-y | |
dc.identifier.uri | http://hdl.handle.net/10012/18508 | |
dc.description | This is a post-peer-review, pre-copyedit version of an article published in Algorithmica. The final authenticated version is available online at: https://doi.org/10.1007/s00453-020-00754-y | en |
dc.description.abstract | 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. | en |
dc.description.sponsorship | 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). | en |
dc.language.iso | en | en |
dc.publisher | Springer Nature | en |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 International | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | graph coloring | en |
dc.subject | forbidden induced subgraph | en |
dc.subject | polynomial algorithm | en |
dc.title | List 3-Coloring Graphs with No Induced P6+rP3 | en |
dc.type | Article | en |
dcterms.bibliographicCitation | Chudnovsky, M., Huang, S., Spirkl, S. et al. List 3-Coloring Graphs with No Induced P6+rP3. Algorithmica 83, 216–251 (2021). https://doi.org/10.1007/s00453-020-00754-y | en |
uws.contributor.affiliation1 | Faculty of Mathematics | en |
uws.contributor.affiliation2 | Combinatorics and Optimization | en |
uws.typeOfResource | Text | en |
uws.peerReviewStatus | Reviewed | en |
uws.scholarLevel | Faculty | en |