Excluded minors in cubic graphs

Neil Robertson, Paul Seymour, Robin Thomas

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


Let G be a cubic graph, with girth at least five, such that for every partition X,Y of its vertex set with |X|,|Y|≥7 there are at least six edges between X and Y. We prove that if there is no homeomorphic embedding of the Petersen graph in G, and G is not one particular 20-vertex graph, then either • G∖v is planar for some vertex v; or • G can be drawn with crossings in the plane, but with only two crossings, both on the infinite region. We also prove several other theorems of the same kind.

Original languageEnglish (US)
Pages (from-to)219-285
Number of pages67
JournalJournal of Combinatorial Theory. Series B
StatePublished - Sep 2019

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Apex graph
  • Cubic
  • Graph minors
  • Petersen graph


Dive into the research topics of 'Excluded minors in cubic graphs'. Together they form a unique fingerprint.

Cite this