2009/12/24 by Guoli Ding, Bogdan Oporowski, Ding, Guoli +5
Mathematics · #05C10 #05C99 #05D10 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C10 #msc:05C99 #msc:05D10
paper · pdf · doi:10.48550/arxiv.0912.4778
To appear in Journal of Combinatorial Theory B. 20 pages. No figures. TeX
arxiv created 2010/11/10 · arxiv updated 2010/11/11
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 K4,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.