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 Pn P n denote the path on n  vertices, and G+H G + 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+P2 r P 1 + P 2 when parameterized by k+r 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 Listk-Coloring is fixed-parameter tractable on graphs with no induced P1+P3 P 1 + P 3 when parameterized by k.
linear forest fixed-parameter tractable k-coloring coloring listk-coloring list coloring h-free