  A graph is $H$-free if it does not contain an induced subgraph isomorphic to
$H$. We denote by $P_k$ and $C_k$ the path and the cycle on $k$ vertices,
respectively. In this paper, we prove that 4-COLORING is NP-complete for
$P_7$-free graphs, and that 5-COLORING is NP-complete for $P_6$-free graphs.
These two results improve all previous results on $k$-coloring $P_t$-free
graphs, and almost complete the classification of complexity of $k$-COLORING
$P_t$-free graphs for $k\ge 4$ and $t\ge 1$, leaving as the only missing case
4-COLORING $P_6$-free graphs. We expect that 4-COLORING is polynomial time
solvable for $P_6$-free graphs; in support of this, we describe a polynomial
time algorithm for 4-COLORING $P_6$-free graphs which are also $P$-free, where
$P$ is the graph obtained from $C_4$ by adding a new vertex and making it
adjacent to exactly one vertex on the $C_4$.
