The  k  -Coloring problem is to test whether a graph can be colored with at most  k  colors such that no two adjacent vertices receive the same color. If a graph  G  does not contain a graph  H  as an induced subgraph, then  G  is called  H  -free. For any fixed graph  H  on at most 6 vertices, it is known that 3-Coloring is polynomial-time solvable on  H  -free graphs whenever  H  is a linear forest and NP-complete otherwise. By solving the missing case  P  2 + P  3 , we prove the same result for 4-Coloring provided that  H  is a fixed graph on at most 5 vertices.
['Petr A. Golovach', 'Daniël Paulusma', 'Jian Song']
4-coloring h-free graphs when h is small