Decomposition of bipartite graphs under degree constraints

Haitze J. Broersma, R.J. Faudree, J.P.M. van den Heuvel, H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

72 Downloads (Pure)

Abstract

Let G = (A, B; E) be a bipartite graph. Let e1, e2 be nonnegative integers, and f1, f2 nonnegative integer-valued functions on V(G) such that ei ≤|E|≤ e1 + e2 and fi(v)≤d(v)≤f1(v) + f2(v) for all v ε V(G) (i = 1, 2). Necessary and sufficient conditions are obtained for G to admit a decomposition in spanning subgraphs G1 = (A, B; E1) and G2 = (A, B; E2) such that |Ei|≤ei and dGi(v)≤fi(v) for all v ε V(G) (i = 1, 2). The result generalizes a known characterization of bipartite graphs with a k-factor. Its proof uses flow theory and is a refinement of the proof of an analogous result due to Folkman and Fulkerson. By applying corresponding flow algorithms, the described decomposition can be found in polynomial time if it exists. As an application, an assignment problem is solved.
Original languageEnglish
Pages (from-to)159-164
Number of pages6
JournalNetworks
Volume23
Issue number23
DOIs
Publication statusPublished - 1993

Keywords

  • METIS-140380
  • IR-71001

Fingerprint Dive into the research topics of 'Decomposition of bipartite graphs under degree constraints'. Together they form a unique fingerprint.

Cite this