List monopolar partitions of claw-free graphs
List monopolar partitions of claw-free graphs
复制标题
列出无爪图的单极划分
DOI：
10.1016/j.disc.2011.08.022
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Jing Huang
中科院分区：
文献类型：
--
作者：
Ross Churchley;Jing Huang
列表单极划分问题询问图 G 与列表 L(v)⊆{0,1},v∈V(G) 是否承认映射 f:V(G)→{0,1}，使得每个 v∈V(G),f−1(0) 的 f(v)∈L(v) 诱导一个独立集，并且 f−1(1) 诱导 G 中派系的不相交并。这个问题一般是 NP 完全的。我们证明，对于无爪图，该问题可以在 O(n2m) 时间内解决，其中 n 和 m 分别是输入图中的顶点和边的数量。
The list monopolar partition problem asks whether a graph G together with lists L(v)⊆{0,1},v∈V(G) admits a mapping f:V(G)→{0,1} such that f(v)∈L(v) for each v∈V(G),f−1(0) 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(n2m) for claw-free graphs where n and m are the numbers of vertices and edges respectively in the input graph.