Graph minors. XIX. Well-quasi-ordering on a surface

Neil Robertson, P. D. Seymour

Research output: Contribution to journalArticle

14 Scopus citations

Abstract

In a previous paper (J. Combin. Theory 48 (1990) 255) we showed that for any infinite set of (finite) graphs drawn in a fixed surface, one of the graphs is isomorphic to a minor of another. In this paper we extend that result in two ways: • we generalize from graphs to hypergraphs drawn in a fixed surface, in which each edge has two or three ends, and • the edges of our hypergraphs are labelled from a well-quasi-order, and the minor relation is required to respect this order. This result is another step in the proof of Wagner's conjecture, that for any infinite set of graphs, one is isomorphic to a minor of another.

Original languageEnglish (US)
Pages (from-to)325-385
Number of pages61
JournalJournal of Combinatorial Theory. Series B
Volume90
Issue number2
DOIs
StatePublished - Mar 2004
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. XIX. Well-quasi-ordering on a surface'. Together they form a unique fingerprint.

  • Cite this