4-coloring $P_6$-free graphs with no induced 5-cycles

Abstract

We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle $C_5$ and no induced 6-vertex path $P_6$.