DOI: 10.1002/jgt.70107 ISSN: 0364-9024
Maximum Partial List H‐Coloring on P5‐Free Graphs in Polynomial Time
Daniel Lokshtanov, Paweł Rzążewski, Saket Saurabh, Roohani Sharma, Meirav ZehaviABSTRACT
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).