×

zbMATH — the first resource for mathematics

Graph minors. XIX: Well-quasi-ordering on a surface. (English) Zbl 1035.05086
Authors’ abstract: In a previous paper [J. Comb. Theory, Ser. B 48, 255–288 (1990; Zbl 0719.05033)] 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: (1) We generalize from graphs to hypergraphs drawn in a fixed surface, in which each edge has two or three ends. (2) The edges of our hypergraph 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.

MSC:
05C83 Graph minors
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Robertson, N.; Seymour, P.D., Graph minors. VI. disjoint paths across a disc, J. combin. theory ser. B, 41, 115-138, (1986) · Zbl 0598.05042
[2] Robertson, N.; Seymour, P.D., Graph minors. VII. disjoint paths on a surface, J. combin. theory ser. B, 45, 212-254, (1988) · Zbl 0658.05044
[3] Robertson, N.; Seymour, P.D., Graph minors IV. tree-width and well-quasi-ordering, J. combin. theory ser. B, 48, 227-254, (1990) · Zbl 0719.05032
[4] Robertson, N.; Seymour, P.D., Graph minors. VIII. A Kuratowski theorem for general surfaces, J. combin. theory ser. B, 48, 255-288, (1990) · Zbl 0719.05033
[5] Robertson, N.; Seymour, P.D., Graph minors. X. obstructions to tree-decomposition, J. combin. theory ser. B, 52, 153-190, (1991) · Zbl 0764.05069
[6] Robertson, N.; Seymour, P.D., Graph minors. XI. circuits on a surface, J. combin. theory ser. B, 60, 72-106, (1994) · Zbl 0799.05016
[7] Robertson, N.; Seymour, P.D., Graph minors. XII. distance on a surface, J. combin. theory ser. B, 64, 240-272, (1995) · Zbl 0840.05016
[8] Robertson, N.; Seymour, P.D., Graph minors. XIV. extending an embedding, J. combin. theory ser. B, 65, 23-50, (1995) · Zbl 0840.05017
[9] Robertson, N.; Seymour, P.D., Graph minors. XVII. taming a vortex, J. combin. theory ser. B, 77, 162-210, (1999) · Zbl 1027.05088
[10] Robertson, N.; Seymour, P.D., Graph minors. XVIII. tree-decompositions and well-quasi-ordering, J. combin. theory ser. B, 89, 77-108, (2003) · Zbl 1023.05111
[11] N. Robertson, P.D. Seymour, Graph Minors. XX. Wagner’s conjecture, submitted for publication. · Zbl 1061.05088
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.