×

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
PDF BibTeX Cite
Full Text: DOI
References:
[1] Diestel, R., Graph theory, Graduate texts in mathematics, 173, (1997), Springer-Verlag New York
[2] Gorbunov, K.Yu., Structural properties of context-free grammars, (1998), Moscow State University · Zbl 0912.68078
[3] 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
[4] 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
[5] Robertson, N.; Seymour, P.D., Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[6] Robertson, N.; Seymour, P.D., Graph minors. X. obstructions to tree-decomposition, J. combin. theory ser. B, 52, 153-190, (1991) · Zbl 0764.05069
[7] Robertson, N.; Seymour, P.D.; Thomas, R., Quickly excluding a planar graph, J. combin. theory ser. B, 62, 323-348, (1994) · Zbl 0807.05023
[8] 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
[9] 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.