List-monopolar partitions of claw-free graphs

Paper with Jing Huang presented at the 8th French Combinatorial Conference

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.

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.

Ross Churchley and Jing Huang [1]

Jing presented this paper at the 8th French Combinatorial Conference.


  1. List monopolar partitions of claw-free graphs. Discrete Mathematics 312(17). Ross Churchley and Jing Huang (2012). ↩︎