Four-coloring P6-free graphs
Sophie Spirkl, Maria Chudnovsky, Mingxian Zhong · Society for Industrial and Applied Mathematics eBooks · 2019
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.