Maximum list $r$-colorable induced subgraphs in $k{P}_3$-free graphs

We show that, for every fixed positive integers $r$ and $k$, \textsc{Max-Weight List $r$-Colorable Induced Subgraph} admits a polynomial-time algorithm on $k{P}_3$-free graphs. This problem is a common generalization of $\text{textsc}Max-WeightIndependentSet$, $\text{textsc}OddCycleTransversal$ and \textsc{List $r$-Coloring}, among others. Our result has several consequences. First, it implies that, for every fixed $r\ge 5$, assuming $\mathsf{P}\mathrm{\ne }\mathsf{N}\mathsf{P}$, \textsc{Max-Weight List $r$-Colorable Induced Subgraph} is polynomial-time solvable on $H$-free graphs if and only if $H$ is an induced subgraph of either $k{P}_3$ or $P_5+k{P}_1$, for some $k\ge 1$. Second, it makes considerable progress toward a complexity dichotomy for $\text{textsc}OddCycleTransversal$ on $H$-free graphs, allowing to answer a question of Agrawal, Lima, Lokshtanov, Rz{ą}{ż}ewski, Saurabh, and Sharma [TALG 2024]. Third, it gives a short and self-contained proof of the known result of Chudnovsky, Hajebi, and Spirkl [Combinatorica 2024] that \textsc{List $r$-Coloring} on $k{P}_3$-free graphs is polynomial-time solvable for every fixed $r$ and $k$. We also consider two natural distance-$d$ generalizations of $\text{textsc}Max-WeightIndependentSet$ and \textsc{List $r$-Coloring} and provide polynomial-time algorithms on $k{P}_3$-free graphs for every fixed integers $r$, $k$, and $d\ge 6$.