## 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**_{0}(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_{0}(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.