Large non-planar graphs and an application to crossing-critical graphs
From MaRDI portal
Publication:631645
DOI10.1016/J.JCTB.2010.12.001zbMATH Open1223.05153arXiv0912.4778OpenAlexW2126687412MaRDI QIDQ631645FDOQ631645
Guoli Ding, Bogdan Oporowski, Robin Thomas, Dirk Vertigan
Publication date: 14 March 2011
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: We 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. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We 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.
Full work available at URL: https://arxiv.org/abs/0912.4778
Extremal problems in graph theory (05C35) Distance in graphs (05C12) Connectivity (05C40) Graph minors (05C83)
Cites Work
Cited In (7)
- Characterizing 2-crossing-critical graphs
- Graphs with at most one crossing
- On the Decay of Crossing Numbers of Sparse Graphs
- Non-planar extensions of subdivisions of planar graphs
- Domination and independence number of large 2-crossing-critical graphs
- Crossing-number critical graphs have bounded path-width
- Non-embeddable extensions of embedded minors
This page was built for publication: Large non-planar graphs and an application to crossing-critical graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q631645)
