Complexity of Coloring Graphs without Paths and Cycles

Pavol Hell, Shenwei Huang

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. M…