×

Minors in large almost-5-connected non-planar graphs. (English) Zbl 1248.05196

Summary: 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 \(K_{6}^{-}\)-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 \(K_{6}^{-}\)-minor.

MSC:

05C83 Graph minors
05C40 Connectivity
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Keywords:

minor; 5-connected
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Diestel, Graph Theory (2000)
[2] Böhme, Linear connectivity forces large complete bipartite minors, J Comb Theory Ser B 99 (3) pp 557– (2009) · Zbl 1214.05061
[3] T. Böhme K. Kawarabayashi J. Maharry B. Mohar K 3, k minors in large 7-connected graphs
[4] Böhme, Ka,k minors in graphs of bounded tree-width, J Comb Theory Ser B 86 pp 133– (2002)
[5] Jakobsen, On certain homomorphism properties of graphs I, Math Scand 31 pp 379– (1972) · Zbl 0258.05126 · doi:10.7146/math.scand.a-11440
[6] Jakobsen, On certain homomorphism properties of graphs II, Math Scand 52 pp 229– (1983) · Zbl 0566.05049 · doi:10.7146/math.scand.a-12004
[7] Jorgensen, Contractions to K8, J Graph Theory 18 pp 431– (1994)
[8] Jorgensen, Vertex partitions of K4,4-minor free graphs, Graphs Comb 17 pp 265– (2001)
[9] Jorgensen, Extremal results for rooted minor problems, J Graph Theory 55 pp 191– (2007)
[10] Juvan, Elimination of local bridges, Math Slovaca 47 pp 85– (1997) · Zbl 0958.05033
[11] K. Kawarabayashi S. Norine R. Thomas P. Wollan K 6 -minors in large 6-connected graphs · Zbl 1379.05105
[12] Maharry, A characterization of graphs with no cube minor, J Comb Theory Ser B 80 pp 179– (2000) · Zbl 1023.05119
[13] Maharry, An excluded minor theorem for the octahedron plus an edge, J Graph Theory 57 pp 124– (2008) · Zbl 1131.05085
[14] Maharry, The structure of projective planar graphs with no K3,4-minor, J Graph Theory 67 (2011)
[15] Oporowski, Typical subgraphs of 3- and 4-connected graphs, J Comb Theory Ser B 57 pp 239– (1993) · Zbl 0728.05041
[16] N. Robertson personal communication
[17] N. Robertson P. Seymour Excluding a graph with one crossing Graph Structure Theory Seattle WA 1991 669 675
[18] Robertson, Quickly excluding a planar graph, J Comb Theory Ser B 62 pp 323– (1994) · Zbl 0807.05023
[19] Robertson, Graph Minors. IX. Disjoint crossed paths, J Comb Theory Ser B 49 pp 40– (1990) · Zbl 0741.05044
[20] Robertson, Paths, Flows, and VLSI-Layout pp 267– (1990)
[21] Thomas, Recent excluded minor theorems, British Combinatorial Conference 1999 (1999) · Zbl 0949.05076
[22] Wagner, Über eine Eigenschaft der ebenen Komplexe, Math Ann 114 pp 570– (1937) · JFM 63.0550.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.