TY - JOUR

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

AU - Robertson, Neil

AU - Seymour, P. D.

N1 - Funding Information:
E-mail address: pds@math.princeton.edu (P.D. Seymour). 1This research was partially supported by NSF Grant DMS 8504054. 2Present address: Mathematics Department, Princeton University, Princeton, NJ 08544, USA.

PY - 2004/3

Y1 - 2004/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=1442330929&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1442330929&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2003.08.005

DO - 10.1016/j.jctb.2003.08.005

M3 - Article

AN - SCOPUS:1442330929

SN - 0095-8956

VL - 90

SP - 325

EP - 385

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -