Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648123 | Discrete Mathematics | 2012 | 5 Pages |
Abstract
The list monopolar partition problem asks whether a graph GG together with lists L(v)⊆{0,1},v∈V(G)L(v)⊆{0,1},v∈V(G) admits a mapping f:V(G)→{0,1}f:V(G)→{0,1} such that f(v)∈L(v)f(v)∈L(v) for each v∈V(G),f−1(0) induces an independent set and f−1(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(n2m) for claw-free graphs where nn and mm are the numbers of vertices and edges respectively in the input graph.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ross Churchley, Jing Huang,