List-monopolar partitions of claw-free graphs

The list monopolar partition problem asks whether a graph $$G$$ together with lists $$L(v) \subseteq {0, 1}$$, $$v \in V(G)$$ admits a mapping $$f: V(G) \rightarrow {0,1}$$ such that $$f(v) \in 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(n^{2}m)$$ 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.