Large non-planar graphs and an application to crossing-critical graphs

Article, Preprint English OPEN
Ding, Guoli ; Oporowski, Bogdan ; Thomas, Robin ; Vertigan, Dirk (2011)
  • Publisher: Elsevier BV
  • Journal: Journal of Combinatorial Theory, Series B, volume 101, issue 2, pages 111-121 (issn: 0095-8956)
  • Related identifiers: doi: 10.1016/j.jctb.2010.12.001
  • Subject: Mathematics - Combinatorics | Theoretical Computer Science | Computational Theory and Mathematics | 05C99, 05C10, 05D10 | Discrete Mathematics and Combinatorics

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... View more
  • References (7)

    1. D. Bokal, R. B. Richter and G. Salazar, Characterization of 2-crossing-critical graphs I: Low connectivity or no V2n minor, manuscript, October 17, 2009.

    2. G. Ding, B. Oporowski, R. Thomas and D. Vertigan, Large 4-connected nonplanar graphs, manuscript, August 1999.

    Baltimore, MD, 2001.

    3. B. Mohar and C. Thomassen, Graphs on surfaces, Johns Hopkins University Press,

    4. B. Oporowski, J. Oxley and R. Thomas, Typical subgraphs of 3- and 4-connected graphs, J. Combin. Theory Ser. B 57 (1993), 239-257.

    5. N. Robertson and P. D. Seymour, Graph Minors IX. Disjoint crossed paths, J. Combin. Theory Ser. B 49 (1990), 40-77.

    6. N. Robertson, P. D. Seymour and R. Thomas, Non-planar extensions of planar graphs, manuscript.

  • Metrics
    No metrics available