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 source 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(n2m) for claw-free graphs where n and m are the numbers of vertices and edges respectively in the input graph.

List-monopolar partitions of claw-free graphs. Ross Churchley and Jing Huang. Discrete Mathematics 312 (17), 2545–2549. September 2012.