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

AbstractThe 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 List k-Coloring problem requires in addition that every vertex u must receive a color from some given set L(u)⊆{1,…,k}. Let Pn denote the path on n vertices, and G+H and rH the disjoint union of two graphs G and H and r copies of H, respectively. We show that List k-Coloring is fixed-parameter tractable on graphs with no induced rP1+P2 when parameterized by k+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 List k-Coloring is fixed-parameter tractable on graphs with no induced P1+P3 when parameterized by k