Rooted grid minors

DOI10.1016/J.JCTB.2016.07.003zbMATH Open1350.05158arXiv1307.8138OpenAlexW2963079069MaRDI QIDQ345092FDOQ345092

Authors: Paul Wollan, Dániel Marx, Paul Seymour 

Publication date: 25 November 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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. This is a lemma for use in a later paper.

Full work available at URL: https://arxiv.org/abs/1307.8138

Recommendations

• Tangles, tree-decompositions and grids in matroids
• Computing with Tangles
• Tangles, trees, and flowers
• Computing with tangles
• Tangles and connectivity in graphs

zbMATH Keywords

treewidthtanglesgrid minors

Mathematics Subject Classification ID

Graph minors (05C83)

Cites Work

• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. V. Excluding a planar graph
• Mangoes and blueberries

Cited In (7)

• Minors for alternating dimaps
• Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs
• Tangles and connectivity in graphs
• Brambles, prisms and grids
• Criticality for multicommodity flows
• Erdős-Pósa property for labeled minors: 2-connected minors
• The complexity of pattern counting in directed graphs, parameterised by the outdegree

This page was built for publication: Rooted grid minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q345092)