Maximum list r-colorable induced subgraphs in kP₃-free graphs

We show that, for every fixed positive integers r and k, {Max-Weight List r-Colorable Induced Subgraph} admits a polynomial-time algorithm on kP₃-free graphs. This problem is a common generalization of {Max-Weight Independent Set}, {Odd Cycle Transversal} and {List r-Coloring}, among others. Our result has several consequences. First, it implies that, for every fixed r ≥ 5, assuming P≠ NP, {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 kP₃ or P₅+kP₁, for some k ≥ 1. Second, it makes considerable progress toward a complexity dichotomy for {Odd Cycle Transversal} on H-free graphs, allowing to answer a question of Agrawal, Lima, Lokshtanov, Rz{{a}}{\.z}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 {List r-Coloring} on kP₃-free graphs is polynomial-time solvable for every fixed r and k. We also consider two natural distance-d generalizations of {Max-Weight Independent Set} and {List r-Coloring} and provide polynomial-time algorithms on kP₃-free graphs for every fixed integers r, k, and d ≥ 6.