𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Ka,k Minors in Graphs of Bounded Tree-Width

✍ Scribed by Thomas Böhme; John Maharry; Bojan Mohar

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
175 KB
Volume
86
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that for any positive integers k and w there exists a constant N ¼ N ðk; wÞ such that every 7-connected graph of tree-width less than w and of order at least N contains K 3;k as a minor. Similar result is proved for K a;k minors where a is an arbitrary fixed integer and the required connectivity depends only on a: These are the first results of this type where fixed connectivity forces arbitrarily large (nontrivial) minors.

📜 SIMILAR VOLUMES

Efficient Parallel Algorithms for Graphs
Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
✍ Jens Lagergren 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 236 KB

We present an efficient parallel algorithm for the tree-decomposition problem Ž 3 . Ž. for fixed width w. The algorithm runs in time O O log n and uses O O n processors on an ARBITRARY CRCW PRAM. The sequential complexity of our tree-decom-Ž 2 . position algorithm is O O n log n . The tree-decomposi

Optimal Parametric Search on Graphs of B
Optimal Parametric Search on Graphs of Bounded Tree-Width
✍ David Fernández-Baca; Giora Slutzki 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 339 KB

We give linear-time algorithms for a class of parametric search problems on weighted graphs of bounded tree-width. We also discuss the implications of our results to approximate parametric search on planar graphs.

Packing k-edge trees in graphs of restri
Packing k-edge trees in graphs of restricted vertex degrees
✍ A.K. Kelmans 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB 👁 1 views

## Abstract Let ${\cal G}^{s}\_{r}$ denote the set of graphs with each vertex of degree at least __r__ and at most __s__, __v__(__G__) the number of vertices, and τ~__k__~ (__G__) the maximum number of disjoint __k__‐edge trees in __G__. In this paper we show that if __G__ ∈ ${\cal G}^{s}\_{2}$ a

Preliminary reconstructions of spring pr
Preliminary reconstructions of spring precipitation in southwestern Turkey from tree-ring width
✍ Ramzi Touchan; Gregg M. Garfin; David M. Meko; Gary Funkhouser; Nesat Erkan; Mal 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 448 KB

## Abstract Two reconstructions of spring (May–June) precipitation have been developed for southwestern Turkey. The first reconstruction (1776–1998) was developed from principal components of nine chronologies of __Cedrus libani, Juniperus excelsa, Pinus brutia__, and __Pinus nigra__. The second re

Long Cycles and 3-Connected Spanning Sub
Long Cycles and 3-Connected Spanning Subgraphs of Bounded Degree in 3-Connected K1, d-Free Graphs
✍ B. Jackson; N.C. Wormald 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 238 KB

Let \(G\) be a 3-connected \(K_{1, d}\)-free graph on \(n\) vertices. We show that \(G\) contains a 3-connected spanning subgraph of maximum degree at most \(2 d-1\). Using an earlier result of ours, we deduce that \(G\) contains a cycle of length at least \(\frac{1}{2} n^{c}\) where \(c=\left(\log