Excluded minors in cubic graphs

Neil Robertson, Paul Seymour, Robin Thomas

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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
Volume138
DOIs
StatePublished - Sep 2019

All Science Journal Classification (ASJC) codes

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

Keywords

  • Apex graph
  • Cubic
  • Graph minors
  • Petersen graph

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

  • Cite this