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: [email protected] (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 -