Optimizing the Graph Minors Weak Structure Theorem

2011/02/28 by Archontia C. Giannopoulou, Giannopoulou, Archontia C., Dimitrios M. Thilikos +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #cs.DM #graph theory and CDMA systems #math.CO #msc:05C83

paper · pdf · doi:10.48550/arxiv.1102.5762

arxiv created 2011/02/28 · arxiv updated 2011/03/01

Abstract

One of the major results of [N. Robertson and P. D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B, 63(1):65--110, 1995], also known as the weak structure theorem, revealed the local structure of graphs excluding some graph as a minor: each such graph G either has small treewidth or contains the subdivision of a wall that can be arranged "bidimensionally" inside G, given that some small set of vertices are removed. We prove an optimized version of that theorem where (i) the relation between the treewidth of the graph and the height of the wall is linear (thus best possible) and (ii) the number of vertices to be removed is minimized.

Cited by

• Forbidding Kuratowski Graphs as Immersions

Related

• On the excluded minor structure theorem for graphs of large treewidth
• The Graph Minors Structure Theorem through Bidimensionality
• Local tree-width, excluded minors, and approximation algorithms
• Linear Connectivity Forces Large Complete Bipartite Minors: the Patch for the Large Tree-Width Case
• A Flat Wall Theorem for Matching Minors in Bipartite Graphs