我们研究了在 $H$-自由图中（列表）$k$-着色的参数化复杂度，其中 $H$ 为线性森林，即若干条路径的并集。首先，以 $k$ 为参数，我们证明：
- 对任意 $s\ge 0$，在 $(P_4+sP_1)$-自由图上进行列表 $k$-着色可在 FPT 时间内求解。
- 在 $2P_2$-自由图上，$k$-着色问题是 W[1]-困难的，这一结果以强形式解决了 Ho`ang 等人在 2010 年提出的长期未解问题。
- 在 $(P_4+P_2)$-自由图上，$k$-着色已经是 NP-困难的。
结合已有的非参数化复杂度结果，这三条结论完整划分了 $H$-自由图中 $k$-着色和列表 $k$-着色（以 $k$ 为参数）的三类情形：FPT、XP 但 W[1]-困难、以及 paraNP-困难。
进一步，我们证明当以 $t$ 为参数时，$P_t$-自由图上的 $3$-着色同样是 W[1]-困难的，回答了 Golovach 等人在 2017 年提出的疑问。
作为对 $(P_4+sP_1)$-自由图上列表 $k$-着色算法的副产物，我们得到：对每个固定的 $s$ 与 $k$，仅存在有限个 $(P_4+sP_1)$-自由的最小 $k$-可着色阻碍图。这验证了 Cameron、Ho`ang 与 Sawada 在 2022 年的猜想，并完成了关于任意图 $H$ 与任意 $k$ 的顶点 $k$-临界 $H$-自由图族是否有限的二分划分。
点评