Highly connected sets and the excluded grid theorem (Q1306423)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Highly connected sets and the excluded grid theorem |
scientific article |
Statements
Highly connected sets and the excluded grid theorem (English)
0 references
29 November 2000
0 references
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.
0 references
graph minors
0 references
excluded grid theorem
0 references
tree-width
0 references
connected sets
0 references