Graph minors. XV: Giant steps
This paper continues the series of structural theorems aimed at characterizing the class of graphs not containing a fixed graph as a minor. The main result of this paper reads: For any surface \(\Sigma\) with \(\text{bd}(\Sigma)=\varnothing\), and any integers \(\kappa,\varphi,\mu\geq 0\) there are integers \(\theta,\lambda,\rho\geq 0\) such that the following holds. Let \({\mathcal T}^*\) be a tangle in a graph \(G\), such that some \(\Sigma\)-span of order \(\geq\theta\), is \((\lambda,\mu)\)-flat. Then either: (i) there is a \(\Sigma\)-span of order \(\geq\varphi\) with \(>\kappa\) independent eyes, or (ii) there is a \(\Sigma'\)-span of order \(\geq\varphi\), where \(\Sigma'\) is a surface obtained by adding a crosscap to \(\Sigma\), or (iii) there is a \({\mathcal T}^*\)-central segregation of \(G\) of type \((\rho,\kappa)\) with an arrangement in \(\Sigma\).
- Linear connectivity forces large complete bipartite minors
- Disjoint homotopic paths and trees in a planar graph
- A partial k-arboretum of graphs with bounded treewidth
- Graph minors. XI: Circuits on a surface
- Graph minors. XVI: Excluding a non-planar graph
- Graph minors. XVII: Taming a vortex
- Excluding a group-labelled graph
- Fixed-parameter tractability of treewidth and pathwidth
- Tree-width of hypergraphs and surface duality
- The parallel complexity of tree embedding problems (extended abstract)
- Some recent progress and applications in graph minor theory
This page was built for publication: Graph minors. XV: Giant steps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1924160)
