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.