List monopolar partitions of claw-free graphs

The list monopolar partition problem asks whether a graph G together with lists L ( v ) ⊆ { 0 , 1 } , v ∈ V ( G ) admits a mapping f : V ( G ) → { 0 , 1 } such that f ( v ) ∈ L ( v ) for each v ∈ V ( G ) , f − 1 ( 0 ) induces an independent set and f − 1 ( 1 ) induces a disjoint union of cliques in G . This problem is NP-complete in general. We show that the problem is solvable in time O ( n 2 m ) for claw-free graphs where n and m are the numbers of vertices and edges respectively in the input graph.