Efficient algorithms for decomposing graphs under degree constraints
Efficient algorithms for decomposing graphs under degree constraints
复制标题
DOI：
10.1016/j.dam.2006.10.005
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
C. Bazgan;Z. Tuza;D. Vanderpooten
中科院分区：
文献类型：
--
作者：
C. Bazgan;Z. Tuza;D. Vanderpooten
Stiebitz [Decomposing graphs under degree constraints，J. Graph Theory 23（1996）321-324]证明了如果图G中的每个顶点v都有度d（v）<$a（v）+b（v）+1（其中a和b是任意给定的非负整数值函数），则G有一个非平凡的顶点划分（A，B）使得dA（v）<$a（v）对于每个v∈A，dB（v）<$b（v）对于每个v∈B。Kaneko [On decomposition of triangle-free graphs under degree constraints，J. Graph Theory 27（1998）7-9]和Diwan [Decomposing graphs with girth at least five under degree constraints，J. Graph Theory 33（2000）237-239]加强了这一结果，证明了假设d（v）n a+B（a，B n 1）或仅假设d（v）n a+B-1（a，B（2）如果G分别不包含短于4或5的圈。原始证明包含非构造性步骤。在本文中，我们给出多项式时间算法，找到这样的分区。还提出了k-划分的建设性推广。
Stiebitz [Decomposing graphs under degree constraints, J. Graph Theory 23 (1996) 321–324] proved that if every vertex v in a graph G has degree d(v)⩾a(v)+b(v)+1 (where a and b are arbitrarily given nonnegative integer-valued functions) then G has a nontrivial vertex partition (A,B) such that dA(v)⩾a(v) for every v∈A and dB(v)⩾b(v) for every v∈B. Kaneko [On decomposition of triangle-free graphs under degree constraints, J. Graph Theory 27 (1998) 7–9] and Diwan [Decomposing graphs with girth at least five under degree constraints, J. Graph Theory 33 (2000) 237–239] strengthened this result, proving that it suffices to assume d(v)⩾a+b (a,b⩾1) or just d(v)⩾a+b-1 (a,b⩾2) if G contains no cycles shorter than 4 or 5, respectively. The original proofs contain nonconstructive steps. In this paper we give polynomial-time algorithms that find such partitions. Constructive generalizations for k-partitions are also presented.