Polynomial treewidth forces a large grid-like-minor

DOI10.1016/j.ejc.2011.09.004zbMath1234.05223arXiv0809.0724MaRDI QIDQ661945

Bruce A. Reed, David R. Wood

Publication date: 11 February 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

large grid minor; large grid-like minor; polynomial treewidth

Mathematics Subject Classification ID

05C83: Graph minors

Related Items

Unnamed Item, Constant Congestion Brambles in Directed Graphs, A General Framework for Hypergraph Coloring, Graphs of low average degree without independent transversals, An edge variant of the Erdős-Pósa property, Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking, Grid minors in damaged grids, The structure of graphs not admitting a fixed immersion, Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles, Graph Minors and Parameterized Algorithm Design, Parameters Tied to Treewidth, On the Parameterised Intractability of Monadic Second-Order Logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique minors in Cartesian products of graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• Quickly deciding minor-closed parameters in general graphs
• Extremal problems for transversals in graphs with bounded degree
• Linearity of grid minors in treewidth with applications through bidimensionality
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Graph minors. V. Excluding a planar graph
• The linear arboricity of graphs
• On complete subgraphs of \(r\)-chromatic graphs
• Highly connected sets and the excluded grid theorem
• Graph searching and a min-max theorem for tree-width
• Quickly excluding a planar graph
• Independent transversals in \(r\)-partite graphs
• The extremal function for complete minors
• Independent transversals in locally sparse graphs
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Independent Transversals and Independent Coverings in Sparse Partite Graphs
• An extremal function for contractions of graphs
• Odd Independent Transversals are Odd
• Hitting all maximum cliques with a stable set using lopsided independent transversals