×

zbMATH — the first resource for mathematics

Graph minors. VIII: A Kuratowski theorem for general surfaces. (English) Zbl 0719.05033
[Part VII, cf. ibid. 45, No.2, 212-254 (1988; Zbl 0658.05044).]
In their eighth papers of a long series of papers towards a proof of Wagner’s conjecture, the authors settle the case of graphs of bounded genus. Hence, 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 every closed surface the list of forbidden subgraphs which characterizes the embeddability in that surface is finite. This answers a question of P. Erdős raised as early as in the 1930’s.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Archdeacon, D, A Kuratowski theorem for the projective plane, () · Zbl 0464.05028
[2] Archdeacon, D; Huneke, P, A Kuratowski theorem for non-orientable surfaces, J. combin. theory ser. B, 46, 173-231, (1989) · Zbl 0616.05034
[3] Glover, H; Huneke, P; Wang, C.S, 103 graphs that are irreducible for the projective plane, J. combin. theory ser. B, 27, 332-370, (1979) · Zbl 0352.05027
[4] Higman, G, Ordering by divisibility in abstract algebras, (), 326-336 · Zbl 0047.03402
[5] Kruskal, J, Well-quasi-ordering, the tree theorem, and Vázsonyi’s conjecture, Trans. amer. math. soc., 95, 210-225, (1960) · Zbl 0158.27002
[6] Kuratowski, K, Sur le problème des courbes gauches en topologie, Fund. math., 15, 271-283, (1930) · JFM 56.1141.03
[7] Robertson, N; Seymour, P.D, Graph minors. III. planar tree-width, J. combin. theory ser. B, 36, 49-64, (1984) · Zbl 0548.05025
[8] 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
[9] Robertson, N; Seymour, P.D, Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[10] 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
[11] 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
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.