Graphs on Surfaces - Tree-width and the excluded minor theorem

Chapter 7 Tree-width and the excluded minor theorem

One of the highlights in the Robertson-Seymour theory on graph minors is the finiteness (for each fixed surface S) of the set of the minimal forbidden minors for S.

Theorem 7.0.1 (Robertson and Seymour [RS90b]) For each surface S, Forb₀(S) is finite.

Ten years ago many graph theorists believed that a self-contained proof of Theorem 7.0.1 would take the entire book. However, now a more accessible proof is possible. We present in Section 7.3 a short proof of Thomassen [Th97c] which is based on two other important results in the Robertson-Seymour theory, namely Theorem 7.2.1 (well-quasi-ordering of graphs of bounded tree-width) and Theorem 7.1.7 (the excluded grid theorem). Well-quasi-ordering of graphs of bounded tree-width was proved in the paper [RS90a] which is lengthy and technical as it provides general machinery for the graph minor theory. A shorter direct proof of that result was obtained by Geelen, Gerards, and Whittle [GGW00p]. However, to prove Theorem 7.0.1, the well-quasi-ordering for graphs of bounded tree-width is needed only for graphs in Forb₀(S). A short proof of this weaker result was recently obtained by Mohar [Mo01] and is presented in Section 7.2. Recently, Diestel, Jensen, Gorbunov, and Thomassen [DJGT99] obtained a short proof of Theorem 7.1.7, which we present in Section 7.1. In Section 7.3 we also summarize the few embedding results from earlier sections that are used in the short proof of Theorem 7.0.1 so that this chapter is self-contained.

Bibliography

[DJGT99] R. Diestel, T. R. Jensen, K. Y. Gorbunov, and C. Thomassen, Highly connected sets and the excluded grid theorem, J. Combin. Theory, Ser. B 75 (1999) 61-73.

[GGW00p] J. F. Geelen, A. M. H. Gerards, and G. Whittle, Branch width and well-quasi-ordering in matroids, manuscript, 2000.

[Mo01] B. Mohar, Graph minors and graphs on surfaces, in Surveys in Combinatorics 2001, Ed. J.W.P. Hirschfeld, Cambridge Univ. Press, Cambridge, 2001, London Mathematical Society Lecture Note Series 288, pp.145-163.

[RS90a] N. Robertson, P. D. Seymour, Graph minors. IV. Tree-width and well-quasi-ordering, J. Combin. Theory Ser. B 48 (1990) 227-254.

[RS90b] N. Robertson, P. D. Seymour, Graph minors. VIII. A Kuratowski theorem for general surfaces, J. Combin. Theory Ser. B 48 (1990) 255-288.

[Th97c] C. Thomassen, A simpler proof of the excluded minor theorem for higher surfaces, J. Combin. Theory Ser. B 70 (1997) 306-311.