Four-coloring P6-free graphs
MetadataShow full item record
In 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.
Cite this version of the work
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong (2019). Four-coloring P6-free graphs. UWSpace. http://hdl.handle.net/10012/18545