Name
Abstract | ||
|---|---|---|
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 d"A(v)=a(v) for every v@?A and d"B(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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.dam.2006.10.005 | Discrete Applied Mathematics |
Keywords | Field | DocType |
constructive generalization,degree constraint,graph decomposition,nonconstructive step,vertex partition,b. kaneko,decomposing graph,polynomial algorithm,efficient algorithm,vertex degree.,j. graph theory,vertex v,nontrivial vertex partition,vertex degree,graph g,nonnegative integer-valued function,value function | Graph theory,Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Vertex (graph theory),Algorithm,Decomposition method (constraint satisfaction),Degree (graph theory),Time complexity,Partition (number theory),Mathematics | Journal |
Volume | Issue | ISSN |
155 | 8 | Discrete Applied Mathematics |
Citations | PageRank | References |
7 | 0.52 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cristina Bazgan | 1 | 679 | 62.76 |
| Zsolt Tuza | 2 | 1889 | 262.52 |
| Daniel Vanderpooten | 3 | 1153 | 74.66 |