Optimizing the graph minors weak structure theorem
A key result in the structural theory of graphs is Robertson, Seymour and Thomas's so-called weak structure theorem for graphs excluding a certain fixed graph as a minor [\textit{N. Robertson} and \textit{P. D. Seymour}, J. Comb. Theory, Ser. B 63, No. 1, 65--110 (1995; Zbl 0823.05038)]. The original theorem is that there is a function \(f: \mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}\) such that for every \(k\in \mathbb{N}\), every \(h\)-vertex graph \(H\) and every graph \(G\), either \(G\) contains \(H\) as a minor, or \(G\) has treewidth at most \(f(h,k)\) or there is a set \(X\) of at most \({h\choose 2}\) vertices (apices) of \(G\) such that \(G\backslash X\) contains as a subgraph a subdivision of a certain graph, the `wall\'\, of height \(k\) which is arranged in \(G\) in a certain `flat\'\, manner (called the flatness condition: we omit its exact definition).NEWLINENEWLINEThe paper under review gives a significant sharpening of the weak structure theorem by firstly, making \(f(h,k)\) a function linear in \(k\) and secondly by reducing the maximum number of apices from \({h\choose 2}\) to \(h-5\). This is optimal as can be shown by considering a \(k\times k\) grid all of whose vertices are adjacent to all vertices in a \(K_{h-5}\). The proof is non-trivially harder than in the original paper of Robertson and Seymour: in particular, it uses their strong structure theory on the global structure of graphs with no \(K_{h}\) minor [\textit{N. Robertson} and \textit{P. D. Seymour}, J. Comb. Theory, Ser. B 89, No. 1, 43--76 (2003; Zbl 1023.05040)] together with facts from [\textit{F. V. Fomin} et al., J. Comb. Theory, Ser. B 101, No. 5, 302--314 (2011; Zbl 1223.05022)].
- Some optimization problems on weak-bisplit graphs
- The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
- Complete graph minors and the graph minor structure theorem
- All minor-minimal apex obstructions with connectivity two
- Forbidding Kuratowski graphs as immersions
- New tools and results in graph minor structure theory
- Upper bounds on the graph minor theorem
- Contraction-bidimensionality of geometric intersection graphs
- Improved bounds for the flat wall theorem
- k-apices of minor-closed graph classes. I: Bounding the obstructions
- A more accurate view of the flat wall theorem
- A new proof of the flat wall theorem
- Compound logics for modification problems
- Contraction bidimensionality of geometric intersection graphs
- Quickly deciding minor-closed parameters in general graphs
This page was built for publication: Optimizing the graph minors weak structure theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2870501)
