کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420966 | 684012 | 2007 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Efficient algorithms for decomposing graphs under degree constraints Efficient algorithms for decomposing graphs under degree constraints](/preview/png/420966.png)
Stiebitz [Decomposing graphs under degree constraints, J. Graph Theory 23 (1996) 321–324] proved that if every vertex vv in a graph G has degree d(v)⩾a(v)+b(v)+1d(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)(A,B) such that dA(v)⩾a(v)dA(v)⩾a(v) for every v∈Av∈A and dB(v)⩾b(v)dB(v)⩾b(v) for every v∈Bv∈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+bd(v)⩾a+b (a,b⩾1a,b⩾1) or just d(v)⩾a+b-1d(v)⩾a+b-1 (a,b⩾2a,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.
Journal: Discrete Applied Mathematics - Volume 155, Issue 8, 15 April 2007, Pages 979–988