We investigate the parameterized complexity of (List) $k$-Coloring in $H$-free graphs, where $H$ is a linear forest (a disjoint union of paths). First, taking $k$ as the parameter, we show:
- For any $s\ge 0$, List $k$-Coloring on $(P_4+sP_1)$-free graphs is fixed‑parameter tractable (FPT).
- $k$-Coloring is W[1]-hard on $2P_2$-free graphs, settling in a strong form the long‑standing open problem posed by Ho`ang et al. in 2010.
- $k$-Coloring is NP‑hard on $(P_4+P_2)$-free graphs.
Together with known classical (non‑parameterized) results, these three statements yield a complete classification of $k$-Coloring and List $k$-Coloring in $H$-free graphs (parameterized by $k$) into the three regimes: FPT, XP but W[1]-hard, and paraNP‑hard.
We also prove that $3$-Coloring is W[1]-hard in $P_t$-free graphs when parameterized by $t$, answering a question of Golovach, Johnson, Paulusma, and Song (2017).
As a by‑product of our algorithm for List $k$-Coloring in $(P_4+sP_1)$-free graphs, we show that for every fixed $s$ and $k$ there are only finitely many $(P_4+sP_1)$-free minimal obstructions to $k$‑colorability. This confirms the conjecture of Cameron, Ho`ang, and Sawada (2022) and completes the dichotomy concerning the finiteness of vertex‑$k$‑critical $H$‑free graphs for any graph $H$ and any $k$.
Review