Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jctb.2010.12.001 | Journal of Chemical Thermodynamics |
Keywords | Field | DocType |
minor,3-connected 2-crossing-critical graph,subdivision isomorphic,minor isomorphic,non-planar graph,integer k,length k,crossing-critical,positive integer k,integer n,n vertex,4-connected non-planar graph,bounded size,subdivision,crossing number,large non-planar graph,planar graph | Discrete mathematics,Wheel graph,Complete graph,Graph toughness,Combinatorics,Graph power,Neighbourhood (graph theory),Cycle graph,1-planar graph,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
101 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
3 | 0.50 | 2 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guoli Ding | 1 | 444 | 51.58 |
| Bogdan Oporowski | 2 | 266 | 23.24 |
| Robin Thomas | 3 | 89 | 11.20 |
| Dirk Vertigan | 4 | 331 | 32.14 |