✦ LIBER ✦

Decomposition of bipartite graphs under degree constraints

✍ Scribed by H. J. Broersma; R. J. Faudree; J. Den Van Heuvel; H. J. Veldman

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 339 KB
Volume: 23
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230230303

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G = (A, B; E) be a bipartite graph. Let e~1~, e~2~ be nonnegative integers, and f~1~, f~2~ nonnegative integer‐valued functions on V(G) such that e~i~ ≦ |E| ≦ e~1~ + e~2~ and f~i~(v) ≦ d(v) ≦ f~1~(v) + f~2~(v) for all v ϵ V(G) (i = 1, 2). Necessary and sufficient conditions are obtained for G to admit a decomposition in spanning subgraphs G~1~ = (A, B; E~1~) and G~2~ = (A, B; E~2~) such that |E~i~| ≦ e~i~ and d~Gi~(v) ≦ f~i~(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. © 1993 by John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

On decomposition of triangle-free graphs

On decomposition of triangle-free graphs under degree constraints

✍ Kaneko, Atsushi 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

We prove that if s and t are positive integers and if G is a triangle-free graph with minimum degree s + t, then the vertex set of G has a decomposition into two sets which induce subgraphs of minimum degree at least s and t, respectively.

Decomposing graphs under degree constrai

Decomposing graphs under degree constraints

✍ Stiebitz, Michael 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB

We prove a conjecture of C. Thomassen: If s and t are non-negative integers, and if G is a graph with minimum degree s + t + 1, then the vertex set of G can be partitioned into two sets which induce subgraphs of minimum degree at least s and t , respectively.

Graph Decompositions Satisfying Extremal

Graph Decompositions Satisfying Extremal Degree Constraints

✍ Paul A. Catlin 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB

## Abstract We show that the vertex set of any graph __G__ with __p__⩾2 vertices can be partitioned into non‐empty sets __V__~1~, __V__~2~, such that the maximum degree of the induced subgraph 〈__V__~i~〉 does not exceed where p^i^ = |__V__^i^|, for __i__=1, 2. Furthermore, the structure of the in

Graph decomposition with constraints on

Graph decomposition with constraints on the connectivity and minimum degree

✍ Carsten Thomassen 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 1 views

## Abstract For each pair __s,t__ of natural numbers there exist natural numbers __f(s,t)__ and __g(s,t)__ such that the vertex set of each graph of connectivity at least __f(s,t)__ (respectively minimum degree at least __g(s,t))__ has a decomposition into sets which induce subgraphs of connectivit

Decomposing graphs with girth at least f

Decomposing graphs with girth at least five under degree constraints

✍ Diwan, Ajit A. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 2 views

We prove that the vertex set of a simple graph with minimum degree at least s + t -1 and girth at least 5 can be decomposed into two parts, which induce subgraphs with minimum degree at least s and t, respectively, where s, t are positive integers ≥ 2.

On the decomposition of kn into complete

On the decomposition of kn into complete bipartite graphs

✍ H. Tverberg 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB 👁 1 views

## Abstract A short proof is given of the impossibility of decomposing the complete graph on __n__ vertices into __n__‐2 or fewer complete bipartite graphs.