Optimizing the Graph Minors Weak Structure Theorem

Details Optimizing the Graph Minors Weak Structure Theorem Optimizing the Graph Minors Weak Structure Theorem

2011-02-28

arxiv.org/abs/1102.5762v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Optimizing the Graph Minors Weak Structure Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimizing the Graph Minors Weak Structure Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimizing the Graph Minors Weak Structure Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-440733