Four-coloring P6-free graphs
Abstract
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.
Collections
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
Other formats