Rooted grid minors

Daniel Marx, Paul Seymour, Paul Wollan

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)428-437
Number of pages10
JournalJournal of Combinatorial Theory. Series B
Volume122
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Rooted grid minors'. Together they form a unique fingerprint.

  • Cite this