Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Well-quasi-ordering infinite graphs with forbidden finite planar minor


Author: Robin Thomas
Journal: Trans. Amer. Math. Soc. 312 (1989), 279-313
MSC: Primary 05C99; Secondary 04A20
DOI: https://doi.org/10.1090/S0002-9947-1989-0932450-9
MathSciNet review: 932450
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that given any sequence $ {G_1},{G_2}, \ldots $ of graphs, where $ {G_1}$ is finite planar and all other $ {G_i}$ are possibly infinite, there are indices $ i,j$ such that $ i < j$ and $ {G_i}$ is isomorphic to a minor of $ {G_j}$ . This generalizes results of Robertson and Seymour to infinite graphs. The restriction on $ {G_1}$ cannot be omitted by our earlier result. The proof is complex and makes use of an excluded minor theorem of Robertson and Seymour, its extension to infinite graphs, Nash-Williams' theory of better-quasi-ordering, especially his infinite tree theorem, and its extension to something we call tree-structures over $ {\text{QO}}$-categories, which includes infinitary version of a well-quasi-ordering theorem of Friedman.


References [Enhancements On Off] (What's this?)

  • [1] F. van Engelen, A. W. Miller and J. Steel, Rigid Borel sets and better quasiorder theory. In [10].
  • [2] H. Friedman, N. Robertson, and P. D. Seymour, The metamathematics of the graph minor theorem. In [10].
  • [3] F. Galvin and K. Prikry, Borel sets and Ramsey's theorem, J. Symbolic Logic 38 (1973), 193-198. MR 0337630 (49:2399)
  • [4] G. Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. (3) 2 (1952), 326-336. MR 0049867 (14:238e)
  • [5] I. Kříž and R. Thomas, The Menger-like property of tree-width of infinite graphs and related compactness results (submitted).
  • [6] J. Kruskal, Well-quasi-ordering, the tree theorem, and Vázsonyi's conjecture, Trans. Amer. Math. Soc. 95 (1960), 210-225. MR 0111704 (22:2566)
  • [7] -, The theory of well-quasi-ordering: a frequently discovered concept, J. Combin. Theory 13 (1972), 297-305. MR 0306057 (46:5184)
  • [8] R. Laver, On Fraissé's order type conjecture, Ann. of Math. 93 (1971), 89-111. MR 0279005 (43:4731)
  • [9] -, Better-quasi-orderings and a class of trees, Studies in Foundations and Combinatorics, Adv. in Math. Supplementary Studies 1 (1978), 31-48. MR 520553 (80c:06005)
  • [10] S. G. Simpson, ed., Logic and combinatorics, Contemp. Math., vol. 65, Amer. Math. Soc., Providence, R.I., 1987. MR 891239 (87m:03004)
  • [11] W. Mader, Wohlquasigeordnete Klassen endlicher Graphen, J. Combin. Theory 12 (1972), 105-122. MR 0297611 (45:6665)
  • [12] C. St. J. A. Nash-Williams, On well-quasi-ordering finite trees, Math. Proc. Cambridge Phil. Soc. 59 (1963), 833-835. MR 0153601 (27:3564)
  • [13] -, On well-quasi-ordering infinite trees, Math. Proc. Cambridge Philos. Soc. 61 (1965), 697-720. MR 0175814 (31:90)
  • [14] -, On better-quasi-ordering transfinite sequences, Math. Proc. Cambridge Philos. Soc. 64 (1968), 273-290. MR 0221949 (36:5001)
  • [15] R. Rado, Partial well-ordering of sets of vectors, Mathematika 1 (1954), 89-95. MR 0066441 (16:576b)
  • [16] N. Robertson and P. D. Seymour, Generalizing Kuratowski's theorem, Congress. Numer. 45 (1984), 129-138. MR 777718 (86f:05058)
  • [17] -, Graph minors II. Algorithmic aspects of tree-width, J. Algorithms 7 (1986), 309-322. MR 855559 (88c:05053)
  • [18] -, Graph minors IV. Tree-width and well-quasi-ordering (submitted).
  • [19] -, Graph minors V. Excluding a planar graph J. Combin. Theory 41 (1986), 92-114. MR 854606 (89m:05070)
  • [20] -, Graph minors VI-XIII (submitted).
  • [21] S. G. Simpson, Bqo theory and Fraissé's conjecture, Recursive Aspects of Descriptive Set Theory, by R. Mansfield and G. Weitkamp, Oxford University Press, 1985, pp. 124-138. MR 786122 (86g:03003)
  • [22] -, Nonprovability of certain combinatorial properties of finite trees, Harvey Friedman's Research on the Foundations of Mathematics (L. A. Harrington et al., (eds.), Elsevier North-Holland, 1985. MR 835255 (87i:03122a)
  • [23] R. Thomas, A counterexample to "Wagner's conjecture" for infinite graphs, Math. Proc. Cambridge Philos. Soc. 103 (1988), 55-57. MR 913450 (88i:05174)
  • [24] -, The tree-width compactness theorem for hypergraphs (submitted).
  • [25] -, A Menger-like property of tree-width. The finite case, J. Combin. Theory Ser. B (to appear). MR 1047553 (92a:05041)
  • [26] -, Infinite graphs without $ {K_4}$ and better-quasi-ordering, manuscript, Prague 1984. (Czech)
  • [27] C. Thomassen, Configurations in graphs of large minimum degree, connectivity or chromatic number, preprint. MR 1018651 (90h:05111)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C99, 04A20

Retrieve articles in all journals with MSC: 05C99, 04A20


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1989-0932450-9
Keywords: Well-quasi-ordering, better-quasi-ordering, minor, infinite graph, Wagner's conjecture
Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society