Sachs’ Linkless Embedding Conjecture

Neil Robertson, Paul Douglas Seymour, Robin Thomas

Research output: Contribution to journalArticle

91 Scopus citations

Abstract

We prove Sachs’ conjecture that a graph can be embedded in 3-space so that it contains no non-trivial link (in the sense of knot theory) if and only if it contains as a minor none of the seven graphs obtainable from K6 by Y - Δ and Δ - Y exchanges. We also show the following: (i) A graph admits such a “linkless” embedding if and only if it admits a "panelled" embedding, one such that every circuit of the graph bounds a disc disjoint from the remainder of the graph. This was a conjecture of Böhme. (ii) An embedding is panelled if and only if for every subgraph, its complement in 3-space has free fundamental group. This extends a theorem of Scharlemann and Thompson, who proved it for planar graphs. (iii) If two panelled embeddings of the same graph are “different,” that is, are not related by an orientation-preserving homeomorphism of the 3-space, then there is a subgraph which is a subdivision of K5 or K3, 3 such that the two induced embeddings of this subgraph are still different.

Original languageEnglish (US)
Pages (from-to)185-227
Number of pages43
JournalJournal of Combinatorial Theory, Series B
Volume64
Issue number2
DOIs
StatePublished - Jan 1 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 'Sachs’ Linkless Embedding Conjecture'. Together they form a unique fingerprint.

  • Cite this