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 six 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 P2+P3, we prove the same result for 4-Coloring provided that H is a fixed graph on at most five vertices.