Amir Nikabadi

Maximum List r-Colorable Induced Subgraphs in $$kP_3$$-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_3$$ -free graphs. This problem is a common generalization of Max-Weight Independent Set, Odd Cycle Transversal and List r-Coloring, amo...