Petersen Family Minors

Neil Robertson, Paul Seymour, Robin Thomas

Research output: Contribution to journalArticle

14 Scopus citations

Abstract

We show that the only graphs with certain connectivity and planarity properties are the Petersen graph and some other more trivial graphs. Then this is used to show that every graph with no minor in the Petersen family (the seven graphs that can be obtained from the Petersen graph by Y - Δ and Δ - Y exchanges) is either decomposable in some sense, or it is a 1-vertex extension of a planar graph, or it has high connectivity in a sense we can use, or it can be converted to one of these by Y - Δ and Δ - Y exchanges. This is a lemma for use in a subsequent paper, where we show that a graph has a “linkless” embedding in 3-space if and only if it has no minor in the Petersen family.

Original languageEnglish (US)
Pages (from-to)155-184
Number of pages30
JournalJournal of Combinatorial Theory, Series B
Volume64
Issue number2
DOIs
StatePublished - Jul 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Petersen Family Minors'. Together they form a unique fingerprint.

Cite this