Rooted grid minors

DOI10.1016/J.JCTB.2016.07.003MaRDI QIDQ345092zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

treewidthtanglesgrid minors

Mathematics Subject Classification ID

Graph minors (05C83)

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.

Recommendations

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

Cites work

• Graph minors. V. Excluding a planar graph
• Graph minors. X: Obstructions to tree-decomposition
• 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)