Maximum Partial List H‐Coloring on P5‐Free Graphs in Polynomial Time

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