  Let $P_t$ and $C_\ell$ denote a path on $t$ vertices and a cycle on $\ell$
vertices, respectively. In this paper we study the $k$-coloring problem for
$(P_t,C_\ell)$-free graphs. Maffray and Morel, and Bruce, Hoang and Sawada,
have proved that 3-colorability of $P_5$-free graphs has a finite forbidden
induced subgraphs characterization, while Hoang, Moore, Recoskie, Sawada, and
Vatshelle have shown that $k$-colorability of $P_5$-free graphs for $k \geq 4$
does not. These authors have also shown, aided by a computer search, that
4-colorability of $(P_5,C_5)$-free graphs does have a finite forbidden induced
subgraph characterization. We prove that for any $k$, the $k$-colorability of
$(P_6,C_4)$-free graphs has a finite forbidden induced subgraph
characterization. We provide the full lists of forbidden induced subgraphs for
$k=3$ and $k=4$. As an application, we obtain certifying polynomial time
algorithms for 3-coloring and 4-coloring $(P_6,C_4)$-free graphs. (Polynomial
time algorithms have been previously obtained by Golovach, Paulusma, and Song,
but those algorithms are not certifying); To complement these results we show
that in most other cases the $k$-coloring problem for $(P_t,C_\ell)$-free
graphs is NP-complete. Specifically, for $\ell=5$ we show that $k$-coloring is
NP-complete for $(P_t,C_5)$-free graphs when $k \ge 4$ and $t \ge 7$; for $\ell
\ge 6$ we show that $k$-coloring is NP-complete for $(P_t,C_\ell)$-free graphs
when $k \ge 5$, $t \ge 6$; and additionally, for $\ell=7$, we show that
$k$-coloring is also NP-complete for $(P_t,C_7)$-free graphs if $k = 4$ and
$t\ge 9$. This is the first systematic study of the complexity of the
$k$-coloring problem for $(P_t,C_\ell)$-free graphs. We almost completely
classify the complexity for the cases when $k \geq 4, \ell \geq 4$, and
identify the last three open cases.
