✦ LIBER ✦

Decomposing a Planar Graph into Degenerate Graphs

✍ Scribed by C. Thomassen

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 477 KB
Volume: 65
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1995.1057

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Decomposing a Planar Graph into an Indep

Decomposing a Planar Graph into an Independent Set and a 3-Degenerate Graph

✍ Carsten Thomassen 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 126 KB

We prove the conjecture made by O. V. Borodin in 1976 that the vertex set of every planar graph can be decomposed into an independent set and a set inducing a 3-degenerate graph.

On decomposing a graph into nontrivial b

On decomposing a graph into nontrivial bonds

✍ Sean McGuinness 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 206 KB

We show that for every 2-connected bipartite graph which is not a multiple edge and which has no K 5 -minor there is an edge-disjoint collection of nontrivial bonds (i.e., not stars) which partition the edges of the graph.

Packing trees into planar graphs

✍ A. García; C. Hernando; F. Hurtado; M. Noy; J. Tejel 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

## Abstract In this study, we provide methods for drawing a tree with __n__ vertices on a convex polygon, without crossings and using the minimum number of edges of the polygon. We apply the results to obtain planar packings of two trees in some specific cases. © 2002 Wiley Periodicals, Inc. J Grap

New upper bounds on the decomposability

New upper bounds on the decomposability of planar graphs

✍ Fedor V. Fomin; Dimitrios M. Thilikos 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB 👁 1 views

## Abstract It is known that a planar graph on __n__ vertices has branch‐width/tree‐width bounded by $\alpha \sqrt {n}$. In many algorithmic applications, it is useful to have a small bound on the constant α. We give a proof of the best, so far, upper bound for the constant α. In particular, for th

Decomposing complete equipartite graphs

Decomposing complete equipartite graphs into short even cycles

✍ Benjamin R. Smith; Nicholas J. Cavenagh 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB

In this article we find necessary and sufficient conditions to decompose a complete equipartite graph into cycles of uniform length, in the case that the length is both even and short relative to the number of parts.

Decomposing complete equipartite graphs

Decomposing complete equipartite graphs into cycles of length 2p

✍ Benjamin R. Smith 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB 👁 1 views

## Abstract It is an open problem to determine whether a complete equipartite graph $K\_m\*{\overline{K}}\_n$ (having __m__ parts of size __n__) admits a decomposition into cycles of arbitrary fixed length $k$ whenever __m__, __n__, and __k__ satisfy the obvious necessary conditions for the existen