On the parameterized complexity of coloring graphs in the absence of a linear forest

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The Listk-Coloring problem requires in addition that every vertex u   must receive a color from some given set L(u)⊆{1,…,k}L(u)⊆{1,…,k}. Let PnPn denote the path on n   vertices, and G+HG+H and rH the disjoint union of two graphs G and H and r copies of H, respectively. We show that Listk-Coloring is fixed-parameter tractable on graphs with no induced rP1+P2rP1+P2 when parameterized by k+rk+r, and that for any fixed integer r, the problem k-Coloring restricted to such graphs allows a polynomial kernel when parameterized by k. Finally, we show that Listk-Coloring is fixed-parameter tractable on graphs with no induced P1+P3P1+P3 when parameterized by k.