# zbMATH — the first resource for mathematics

Highly connected sets and the excluded grid theorem. (English) Zbl 0949.05075
In their work on graph minors, Robertson and Seymour prove that the class of graphs without a fixed minor $$X$$ has bounded tree-width if and only if $$X$$ is planar. This is quickly seen to be equivalent to the result that for every $$r$$ there is a $$k$$ such that every graph of tree-width at least $$k$$ has an $$r \times r$$ grid minor. The authors give a new short proof of this excluded grid theorem.
The authors also propose a simple obstruction to small tree-width. A set $$X$$ of at least $$k$$ vertices is $$k$$-connected in a graph $$G$$ if every pair of subsets of $$X$$ of size $$j \leq k$$ are joined by $$j$$ disjoint paths. The authors show that a graph has small tree-width if and only if it has no large highly connected sets of vertices.
This work is a nice contribution to the growing literature on graph minors.

##### MSC:
 05C83 Graph minors
##### Keywords:
graph minors; excluded grid theorem; tree-width; connected sets
Full Text:
##### References:
  Diestel, R., Graph theory, Graduate texts in mathematics, 173, (1997), Springer-Verlag New York  Gorbunov, K.Yu., Structural properties of context-free grammars, (1998), Moscow State University · Zbl 0912.68078  Reed, B.A., Tree-width and tangles: A new connectivity measure and some applications, Surveys in combinatorics, (1997), Cambridge Univ. Press, p. 87-162 · Zbl 0895.05034  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  Robertson, N.; Seymour, P.D., Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055  Robertson, N.; Seymour, P.D., Graph minors. X. obstructions to tree-decomposition, J. combin. theory ser. B, 52, 153-190, (1991) · Zbl 0764.05069  Robertson, N.; Seymour, P.D.; Thomas, R., Quickly excluding a planar graph, J. combin. theory ser. B, 62, 323-348, (1994) · Zbl 0807.05023  Thomassen, C., A simpler proof of the excluded minor theorem for higher surfaces, J. combin. theory ser. B, 70, 306-311, (1997) · Zbl 0882.05053  Thomassen, C., Embeddings and minors, () · Zbl 0851.05043
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.