𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Highly Connected Sets and the Excluded Grid Theorem

✍ Scribed by Reinhard Diestel; Tommy R. Jensen; Konstantin Yu. Gorbunov; Carsten Thomassen

Book ID
102583358
Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
228 KB
Volume
75
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

We present a short proof of the excluded grid theorem of Robertson and Seymour, the fact that a graph has no large grid minor if and only if it has small tree-width. We further propose a very simple obstruction to small tree-width inspired by that proof, showing that a graph has small tree-width if and only if it contains no large highly connected set of vertices.

πŸ“œ SIMILAR VOLUMES

An excluded minor theorem for the octahe
An excluded minor theorem for the octahedron
✍ Maharry, John πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 221 KB

In this article it is shown that every 4-connected graph that does not contain a minor isomorphic to the octahedron is isomorphic to the square of an odd cycle.

An excluded minor theorem for the Octahe
An excluded minor theorem for the Octahedron plus an edge
✍ John Maharry πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 117 KB

## Abstract Let __G__ be the unique 4‐connected simple graph obtained by adding an edge to the Octahedron. Every 4‐connected graph that does not contain a minor isomorphic to __G__ is either planar or the square of an odd cycle. Β© 2007 Wiley Periodicals, Inc. J Graph Theory 57: 124–130, 2008