@article {IOPORT.06082063,
    author       = {Couturier, Jean-Fran\c{c}ois and Golovach, Petr A. and Kratsch, Dieter and Paulusma, Dani\"el},
    title        = {On the parameterized complexity of coloring graphs in the absence of a linear forest.},
    year         = {2012},
    journal      = {Journal of Discrete Algorithms},
    volume       = {15},
    issn         = {1570-8667},
    pages        = {56-62},
    publisher    = {Elsevier Science B.V., Amsterdam},
    doi          = {10.1016/j.jda.2012.04.008},
    abstract     = {Summary: 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 {\sc List $k$-Coloring} problem requires in addition that every vertex $u$ must receive a color from some given set $L(u)\subseteq \{1,\dots ,k\}$. Let $P_{n}$ 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 {\sc List $k$-Coloring} is fixed-parameter tractable on graphs with no induced $rP_{1}+P_{2}$ when parameterized by $k+r$, and that for any fixed integer $r$, the problem {\sc $k$-Coloring} restricted to such graphs allows a polynomial kernel when parameterized by $k$. Finally, we show that {\sc List $k$-Coloring} is fixed-parameter tractable on graphs with no induced $P_{1}+P_{3}$ when parameterized by $k$.},
    identifier   = {06082063},
}