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.
展开▼
