Minors in large almost-5-connected non-planar graphs
✍ Scribed by Ken-Ichi Kawarabayashi; John Maharry
- Publisher
- John Wiley and Sons
- Year
- 2011
- Tongue
- English
- Weight
- 196 KB
- Volume
- 71
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
It is shown that every sufficiently large almost‐5‐connected non‐planar graph contains a minor isomorphic to an arbitrarily large graph from one of six families of graphs. The graphs in these families are also almost‐5‐connected, by which we mean that they are 4‐connected and all 4‐separations contain a “small” side.
As a corollary, every sufficiently large almost‐5‐connected non‐planar graph contains both a K~3, 4~‐minor and a ‐minor. The connectivity condition cannot be reduced to 4‐connectivity, as there are known infinite families of 4‐connected non‐planar graphs that do not contain a K~3, 4~‐minor. Similarly, there are known infinite families of 4‐connected non‐planar graphs that do not contain a ‐minor.