List-monopolar partitions of claw-free graphs

Shortly after solving the monopolar partition problem for line graphs, Jing and I realized that our solution could be used to solve the "precoloured" version of the problem, and then further extended to claw-free graphs.

List monopolar partitions of claw-free graphs. Discrete Mathematics 312(17). Ross Churchley and Jing Huang (2012). The list monopolar partition problem asks whether a graph GG together with lists L(v){0,1}L(v) \subseteq \{0, 1\}, vV(G)v \in V(G) admits a mapping f:V(G){0,1}f: V(G) \rightarrow \{0,1\} such that f(v)L(v)f(v) \in L(v) for each source induces an independent set and f1(1)f^{-1}(1) induces a disjoint union of cliques in GG. This problem is NP-complete in general. We show that the problem is solvable in time O(n2m)O(n^{2}m) for claw-free graphs where nn and mm are the numbers of vertices and edges respectively in the input graph.