Polynomial treewidth forces a large grid-like-minor
From MaRDI portal
Publication:661945
DOI10.1016/j.ejc.2011.09.004zbMath1234.05223arXiv0809.0724OpenAlexW2066666508MaRDI QIDQ661945
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
Related Items (12)
An edge variant of the Erdős-Pósa property ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Constant Congestion Brambles in Directed Graphs ⋮ A General Framework for Hypergraph Coloring ⋮ Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking ⋮ Grid minors in damaged grids ⋮ Graphs of low average degree without independent transversals ⋮ Parameters Tied to Treewidth ⋮ The structure of graphs not admitting a fixed immersion ⋮ Unnamed Item ⋮ On the Parameterised Intractability of Monadic Second-Order Logic ⋮ Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Polynomial treewidth forces a large grid-like-minor
