Highly connected sets and the excluded grid theorem
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.
- A simpler proof of the excluded minor theorem for higher surfaces
- Graph minors. IV: Tree-width and well-quasi-ordering
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- scientific article; zbMATH DE number 1025912 (Why is no real title available?)
- scientific article; zbMATH DE number 1057879 (Why is no real title available?)
- scientific article; zbMATH DE number 863474 (Why is no real title available?)
- On a complexity of the formula \((A\bigvee B) \Rightarrow C\)
- Quickly excluding a planar graph
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Linear connectivity forces large complete bipartite minors
- Branch-width and Rota's conjecture
- The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
- Graph minor hierarchies
- Branch-width and well-quasi-ordering in matroids and graphs.
- Embedding grids in surfaces
- On the excluded minor structure theorem for graphs of large tree-width
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- Characterising \(k\)-connected sets in infinite graphs
- Sparse obstructions for minor-covering parameters
- Half-integral packing of odd cycles through prescribed vertices
- Tree-width and planar minors
- Contraction obstructions for treewidth
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Minors in graphs of large _r-girth
- Treewidth of grid subsets
- \(K_{6}\) minors in 6-connected graphs of bounded tree-width
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- Edge-disjoint odd cycles in 4-edge-connected graphs
- On 3-connected graphs of path-width at most three
- Fixed-parameter tractability of treewidth and pathwidth
- Graph minors and parameterized algorithm design
- Low polynomial exclusion of planar graph patterns
- Parameters tied to treewidth
- Planar k-path in subexponential time and polynomial space
- Coloring immersion-free graphs
- Towards the graph minor theorems for directed graphs
- An Improved Algorithm for Finding Cycles Through Elements
- Graph minors: generalizing Kuratowski's theorem
- Fast balanced partitioning is hard even on grids and trees
- Connectivity and tree structure in finite graphs
- Grid minors in damaged grids
- The disjoint paths problem in quadratic time
- Linkless and flat embeddings in 3-space
- Packing cycles through prescribed vertices under modularity constraints
- Forcing a Kr minor by high external connectivity
- On the block number of graphs
- Counting Answers to Existential Questions
- Half-integral linkages in highly connected directed graphs
- Contraction-bidimensionality of geometric intersection graphs
- Minor-Closed Graph Classes with Bounded Layered Pathwidth
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs
- List-coloring graphs without subdivisions and without immersions
- Characterising graphs with no subdivision of a wheel of bounded diameter
- Polynomial treewidth forces a large grid-like-minor
- \(K_{6}\) minors in large 6-connected graphs
- A new proof of the flat wall theorem
- On the size of two minimal linkages
- Graph parameters, universal obstructions, and WQO
- Grid minors and products
- What is on his mind?
- Contraction bidimensionality of geometric intersection graphs
- Some recent progress and applications in graph minor theory
- Achievable sets, brambles, and sparse treewidth obstructions
- Treewidth lower bounds with brambles
- Linearity of grid minors in treewidth with applications through bidimensionality
- Treewidth computations. I: Upper bounds
- Tree-width of graphs without a \(3\times 3\) grid minor
This page was built for publication: Highly connected sets and the excluded grid theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1306423)
