Abstract
Intuitively, a tangle of large order in a graph is a highly-connected part of the graph, and it is known that if a graph has a tangle of large order then it has a large grid minor. Here we show that for any k, if G has a tangle of large order and Z is a set of vertices of cardinality k that cannot be separated from the tangle by any separation of order less than k, then G has a large grid minor containing Z, in which the members of Z all belong to the outside of the grid.
Original language | English (US) |
---|---|
Pages (from-to) | 428-437 |
Number of pages | 10 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 122 |
DOIs | |
State | Published - Jan 1 2017 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- Grid minors
- Tangles
- Treewidth