Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid
From MaRDI portal
Publication:2904769
DOI10.4230/LIPICS.STACS.2012.278zbMATH Open1244.05212MaRDI QIDQ2904769FDOQ2904769
Authors: Ken-ichi Kawarabayashi, Yusuke Kobayashi 
Publication date: 23 August 2012
Recommendations
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Towards tight(er) bounds for the excluded grid theorem
- Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
- Polynomial bounds for the grid-minor theorem
- Linearity of grid minors in treewidth with applications through bidimensionality
Cited In (18)
- Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction
- A new proof of the flat wall theorem
- Contraction bidimensionality of geometric intersection graphs
- Grid minors in damaged grids
- Linearity of grid minors in treewidth with applications through bidimensionality
- Edge-disjoint odd cycles in 4-edge-connected graphs
- Contraction-bidimensionality of geometric intersection graphs
- Towards tight(er) bounds for the excluded grid theorem
- Rank-width and tree-width of \(H\)-minor-free graphs
- Coloring immersion-free graphs
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Low polynomial exclusion of planar graph patterns
- Tree-width and planar minors
- Towards the graph minor theorems for directed graphs
- The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
- Explicit linear kernels for packing problems
- Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
- Extension complexity of the correlation polytope
This page was built for publication: Linear min-max relation between the treewidth of \(H\)-minor-free graphs and its largest grid
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904769)
