✦ LIBER ✦

Randomly decomposable graphs

✍ Scribed by Sergio Ruiz

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 362 KB
Volume: 57
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(85)90161-x

No coin nor oath required. For personal study only.

✦ Synopsis

A nonempty graph G is randomly H-decomposable if every family of edge-disjoint subgraphs of G, each subgraph isomorphic to H, can be extended to an H-decomposition of G. A characterization of those randomly H-decomposable graphs is given whenever H has two edges. Some related questions are discussed.

By a decomposition of a nonempty graph G is meant a family of subgraphs G1, G2,..., Gk of G such that their edge sets form a partition of the edge set of 0012-365X/85/$3.30

📜 SIMILAR VOLUMES

Recognizing decomposable graphs

✍ V. Chvátal 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

## Abstract A graph is called decomposable if its vertices can be colored red and blue in such a way that each color appears on at least one vertex but each vertex v has at most one neighbor having a different color from v. We point out a simple and efficient algorithm for recognizing decomposable

Randomly matchable graphs

✍ David P. Summer 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB

## Abstract A graph is defined to be randomly matchable if every matching of __G__ can be extended to a perfect matching. It is shown that the connected randomly matchable graphs are precisely __K__~2__n__~ and __K~n,n~__ (__n__ ≥ 1).

Decomposing a Planar Graph into Degenera

Decomposing a Planar Graph into Degenerate Graphs

✍ C. Thomassen 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 477 KB

We prove the conjecture made by $\mathrm{O}$. V. Borodin in 1976 that the vertex set of any planar graph can be decomposed into two sets such that one of them induces a 3-degenerate graph and the other induces a 2-degenerate graph. that is, a forest. c. 1995 Academic Press. Inc.

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.

Decomposing Ends of Locally Finite Graph

Decomposing Ends of Locally Finite Graphs

✍ Heinz Adolf Jung; Peter Niemeyer 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 905 KB

An important invariant of translations of infinite locally finite graphs is that of a direction as introduced by HALIN. This invariant gives not much information if the translation is not a proper one. A new refined concept of directions is investigated. A double ray D of a graph X is said to be me

Two-colourings that decompose perfect gr

Two-colourings that decompose perfect graphs

✍ Vašek Chvátal; William J Lenhart; Najiba Sbihi 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 435 KB