dc.contributor.author | Chudnovsky, Maria | |
dc.contributor.author | Spirkl, Sophie | |
dc.contributor.author | Zhong, Mingxian | |
dc.date.accessioned | 2024-04-05 13:00:43 (GMT) | |
dc.date.available | 2024-04-05 13:00:43 (GMT) | |
dc.date.issued | 2024 | |
dc.identifier.uri | https://doi.org/10.1137/18m1234837 | |
dc.identifier.uri | http://hdl.handle.net/10012/20418 | |
dc.description.abstract | This is the first paper in a series whose goal is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial-time algorithm that determines if a special kind of precoloring of a P6-free graph has a precoloring extension, and constructs such an extension if one exists. Combined with the main result of the second paper of the series, this gives a complete solution to the problem | en |
dc.description.sponsorship | NSF, DMS-1550991 || US Army Research Office, W911NF-16-1-0404 || ERC, 320924. | en |
dc.language.iso | en | en |
dc.publisher | Society for Industrial and Applied Mathematics | en |
dc.relation.ispartofseries | SIAM Journal on Computing;53(1) | |
dc.rights | Attribution 4.0 International | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | * |
dc.subject | coloring | en |
dc.subject | induced subgraph | en |
dc.subject | algorithm | en |
dc.subject | path | en |
dc.title | Four-coloring P6-free graphs. I. Extending an excellent precoloring. | en |
dc.type | Article | en |
dcterms.bibliographicCitation | Chudnovsky, M., Spirkl, S., & Zhong, M. (2024). Four-coloring \(p_6\)-free graphs. i. extending an excellent precoloring. SIAM Journal on Computing, 53(1), 111–145. | 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 |