# 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 Mathematics312(17). Ross Churchley and Jing Huang (2012). 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.