✦ LIBER ✦

Decomposing graphs under degree constraints

✍ Scribed by Stiebitz, Michael

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 246 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199611)23:3<321::aid-jgt12>3.0.co;2-h

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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.

Decomposition of bipartite graphs under

Decomposition of bipartite graphs under degree constraints

✍ H. J. Broersma; R. J. Faudree; J. Den Van Heuvel; H. J. Veldman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 339 KB

## 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)__ f

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.

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

Connectedness of digraphs and graphs und

Connectedness of digraphs and graphs under constraints on the conditional diameter

✍ X. Marcote; C. Balbuena; J. Fàbrega 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 206 KB