×

Large non-planar graphs and an application to crossing-critical graphs. (English) Zbl 1223.05153

The authors prove that, for every positive integer \(k\), there is an integer \(N\) such that every 4-connected non-planar graph with at least \(N\) vertices has a minor isomorphic to \(K_{4,k}\), the graph obtained from a cycle of length \(2k+1\) by adding an edge joining every pair of vertices at distance exactly \(k\), or the graph obtained from a cycle of length \(k\) by adding two vertices adjacent to each other and to every vertex on the cycle. They deduce that for every integer \(k\) there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length \(2k\) by joining all pairs of diagonally opposite vertices.

MSC:

05C40 Connectivity
05C83 Graph minors
05C12 Distance in graphs
05C35 Extremal problems in graph theory

Keywords:

graph minors
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D. Bokal, R.B. Richter, G. Salazar, Characterization of 2-crossing-critical graphs I: Low connectivity or no \(V_{2 n}\); D. Bokal, R.B. Richter, G. Salazar, Characterization of 2-crossing-critical graphs I: Low connectivity or no \(V_{2 n}\)
[2] G. Ding, B. Oporowski, R. Thomas, D. Vertigan, Large 4-connected nonplanar graphs, manuscript, August 1999.; G. Ding, B. Oporowski, R. Thomas, D. Vertigan, Large 4-connected nonplanar graphs, manuscript, August 1999.
[3] Mohar, B.; Thomassen, C., Graphs on Surfaces (2001), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0979.05002
[4] Oporowski, B.; Oxley, J.; Thomas, R., Typical subgraphs of 3- and 4-connected graphs, J. Combin. Theory Ser. B, 57, 239-257 (1993) · Zbl 0728.05041
[5] Robertson, N.; Seymour, P. D., Graph minors IX. Disjoint crossed paths, J. Combin. Theory Ser. B, 49, 40-77 (1990) · Zbl 0741.05044
[6] N. Robertson, P.D. Seymour, R. Thomas, Non-planar extensions of planar graphs, manuscript.; N. Robertson, P.D. Seymour, R. Thomas, Non-planar extensions of planar graphs, manuscript.
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.