Maximum List r-Colorable Induced Subgraphs in $$kP_3$$-Free Graphs

Abstract

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_3$$ -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 \ge 5$$ , assuming $$\textsf{P}\ne \textsf{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_3$$ or $$P_5+kP_1$$ , for some $$k \ge 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ążewski, Saurabh, and Sharma [ACM Trans. Algorithms 2025]. 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_3$$ -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_3$$ -free graphs for every fixed integers r, k, and $$d \ge 6$$ .