Prof. Meirav Zehavi

In this article we show that Maximum Partial List (Formula presented.) -Coloring is polynomial-time solvable on (Formula presented.) -free graphs for every fixed graph (Formula presented.). In particular, this implies that Maximum (Formula presented.) -Colorable Subgraph is polynomial-time solvable on (Formula presented.) -free graphs. This answers an open question from Agrawal, Lima, Lokshtanov, Rzążewski, Saurabh, and Sharma [SODA 2024]. This also improves the (Formula presented.) -time algorithm for Maximum Partial (Formula presented.) -Coloring, where (Formula presented.) is the size of the largest clique in (Formula presented.), by Chudnovsky, King, Pilipczuk, Rzążewski, and Spirkl [SIDMA 2021], to polynomial-time algorithm (independent of the maximum clique size of the graph).