𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Decompositions of graphs into forests with bounded maximum degree

✍ Scribed by Mirosław Truszczyński

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
995 KB
Volume
98
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Truszczydski, M., Decompositions of graphs into forests with bounded maximum degree, Discrete Mathematics 98 (1991) 207-222.

📜 SIMILAR VOLUMES

On Induced Ramsey Numbers for Graphs wit
On Induced Ramsey Numbers for Graphs with Bounded Maximum Degree
✍ Tomasz Łuczak; Vojtěch Rödl 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 435 KB

For graphs G and H we write G wÄ ind H if every 2-edge colouring of G yields an induced monochromatic copy of H. The induced Ramsey number for H is defined as r ind (H)=min[ |V(G)|: G wÄ ind H]. We show that for every d 1 there exists an absolute constant c d such that r ind (H n, d ) n cd for every

The decompositions of line graphs, middl
The decompositions of line graphs, middle graphs and total graphs of complete graphs into forests
✍ Jin Akiyama; Takashi Hamada 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 461 KB

We construct decompositions of L(K,,), M(K,,) and T(K,,) into the minimum number of line-disjoint spanning forests by applying the usual criterion for a graph to be eulerian. This gives a realization of the arboricity of each of these three graphs. ## 1. Preliminaries In this paper a graph is cons

Packing two copies of a sparse graph int
Packing two copies of a sparse graph into a graph with restrained maximum degree
✍ Hong Wang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

## Abstract We show that if a tree __T__ is not a star, then there is an embedding σ of __T__ in the complement of __T__ such that the maximum degree of __T__∪σ(__T__) is at most Δ(__T__)+2. We also show that if __G__ is a graph of order __n__ with __n__−1 edges, then with several exceptions, there

The maximum number of edges in 2K2-free
The maximum number of edges in 2K2-free graphs of bounded degree
✍ F.R.K. Chung; A. Gyárfás; Z. Tuza; W.T. Trotter 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 481 KB

A graph is 2K,-free if it does not contain an independent pair of edges as an induced subgraph. We show that if G is 2K,-free and has maximum degree A(G) = D, then G has at most 5D2/4 edges if D is even. If D is odd, this bound can be improved to (5D\* -20 + 1)/4. The extremal graphs are unique.

Vertex decompositions of sparse graphs i
Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
✍ O. V. Borodin; A. O. Ivanova; M. Montassier; P. Ochem; A. Raspaud 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A graph __G__ is (__k__,0)‐colorable if its vertices can be partitioned into subsets __V__~1~ and __V__~2~ such that in __G__[__V__~1~] every vertex has degree at most __k__, while __G__[__V__~2~] is edgeless. For every integer __k__⩾0, we prove that every graph with the maximum average