Minors in large almost‐5‐connected non‐planar graphs |
| |
Authors: | Ken‐Ichi Kawarabayashi John Maharry |
| |
Institution: | 1. National Institute of Informatics, 2‐1‐2, Hitotsubashi Chiyoda‐ku, , Tokyo 101‐8430, Japan;2. Department of Mathematics, Ohio State University, , Columbus, Ohio |
| |
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 K3, 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 K3, 4‐minor. Similarly, there are known infinite families of 4‐connected non‐planar graphs that do not contain a ‐minor. |
| |
Keywords: | minor 5‐connected |
|
|