DECOMPOSITION OF BIPARTITE GRAPHS UNDER DEGREE CONSTRAINTS

Let G = (A, B; E) be a bipartite graph. Let e1, e2 be nonnegative inte gers, and f1, f2 nonnegative integer-valued functions on V(G) such tha t e(i) less-than-or-equal-to Absolute value of E less-than-or-equal-to e1 + e2 and f(i)(v) less-than-or-equal-to d(v) less-than-or-equal-to f1(v) + f2(V) for all v is-an-element-of V(G) (i = 1, 2). Necessary an d sufficient conditions are obtained for G to admit a decomposition in spanning subgraphs G1 = (A, B; E1) and G2 = (A, B; E2) such that \E(i )\ less-than-or-equal-to e(i) and d(Gi)(V) less-than-or-equal-to f(i)( v) for all v is-an-element-of V(G) (i = 1, 2). The result generalizes a known characterization of bipartite graphs with a k-factor. Its proo f uses flow theory and is a refinement of the proof of an analogous re sult due to Folkman and Fulkerson. By applying corresponding flow algo rithms, the described decomposition can be found in polynomial time if it exists. As an application, an assignment problem is solved.