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, Rza\. zewski, 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.