𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Constructing trees in bipartite graphs

✍ Scribed by U. Schulte

Book ID
103060897
Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
227 KB
Volume
154
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we shall show that if G = (V,E) is a bipartite graph with more than (a -1)j YJ + (b -1)1X1 -(a -l)(b -1) edges, where (X, Y) is a vertex-partition for G and a < b are natural numbers with a < 1x1, b < 1 YI, then G contains every tree T with bipartitenumbers a < b. This result is related to Ramsey-theory for trees.

πŸ“œ SIMILAR VOLUMES

Steiner trees in uniformly quasi-biparti
Steiner trees in uniformly quasi-bipartite graphs
✍ Clemens GrΓΆpl; Stefan Hougardy; Till Nierhoff; Hans JΓΌrgen PrΓΆmel πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 89 KB

The area of approximation algorithms for the Steiner tree problem in graphs has seen continuous progress over the last years. Currently the best approximation algorithm has a performance ratio of 1.550. This is still far away from 1.0074, the largest known lower bound on the achievable performance r

Two trees in maximal planar bipartite gr
Two trees in maximal planar bipartite graphs
✍ Gerhard Ringel πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 127 KB

## Abstract It is proven that each maximal planar bipartite graph is decomposable into two trees. Β© 1993 John Wiley & Sons, Inc.