Upper Bounds on the Size of Obstructions and Intertwines

✍ Scribed by Jens Lagergren

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 417 KB
• Volume: 73
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1997.1788

✦ Synopsis

We give an exponential upper bound in p 4 on the size of any obstruction for path-width at most p. We give a doubly exponential upper bound in k 5 on the size of any obstruction for tree-width at most k. We also give an upper bound on the size of any intertwine of two given trees T and T $. The bound is exponential in O(m 2 log m) where m max( |V(T)|, |V(T $)| ). Finally, we give an upper bound on the size of any intertwine of two given planar graphs H and H$. This bound is triply exponential in O(m 5 ) where m max(|V(H)|, |V(H$)|). We introduce the concept of l-length of a family of graphs L. We prove constructively that, if a minor closed family L has finite p-length and has obstructions of path-width at most p, then L has a finite number of obstructions. Our proof gives a general upper bound, in terms p and the p-length, on the size of any obstruction for L. We obtain a second general upper bound for the case where the obstructions have bounded tree-width. We obtain our upper bounds on obstruction sizes by giving, for the considered family L and an appropriate integer l, an upper bound on the l-length of L and applying one of the two general bounds.