Graph minors. VIII. A kuratowski theorem for general surfaces

Neil Robertson, P. D. Seymour

Research output: Contribution to journalArticle

83 Scopus citations

Abstract

We prove that for any infinite set of graphs of bounded genus, some member of the set is isomorphic to a minor of another. As a consequence, for any surface Σ there is a finite list of graphs, such that a general graph may be drawn in Σ if an only if it topologically contains none of the graphs in the list.

Original languageEnglish (US)
Pages (from-to)255-288
Number of pages34
JournalJournal of Combinatorial Theory, Series B
Volume48
Issue number2
DOIs
StatePublished - Jan 1 1990
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 'Graph minors. VIII. A kuratowski theorem for general surfaces'. Together they form a unique fingerprint.

  • Cite this