zbMATH — the first resource for mathematics

Graph minors. XV: Giant steps. (English) Zbl 0860.05023
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\).

05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX Cite
Full Text: DOI