Show simple item record

dc.contributor.authorChudnovsky, Maria
dc.contributor.authorSpirkl, Sophie
dc.contributor.authorZhong, Mingxian 16:17:20 (GMT) 16:17:20 (GMT)
dc.description© Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong | ACM} 2019. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms,
dc.description.abstractIn this paper we present 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.en
dc.description.sponsorshipSupported by NSF grant DMS-1550991 and US Army Research Office grant W911NF-16-1-0404.en
dc.publisherAssociation for Computing Machineryen
dc.subjectforbidden induced subgraphen
dc.titleFour-coloring P6-free graphsen
dc.typeBook Chapteren
dcterms.bibliographicCitationChudnovsky, M., Spirkl, S., & Zhong, M. (2019). Four-coloring P6-free graphs. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 1239–1256). Society for Industrial and Applied Mathematics.
uws.contributor.affiliation1Faculty of Mathematicsen
uws.contributor.affiliation2Combinatorics and Optimizationen

Files in this item


This item appears in the following Collection(s)

Show simple item record


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