Upper Bounds on the Size of Obstructions and Intertwines

We give an exponential upper bound inp4on the size of any obstruction for path-width at mostp. We give a doubly exponential upper bound ink5 on the size of any obstruction for tree-width at mostk. We also give an upper bound on the size of any intertwine of two given treesTandT′. The bound is exponential inO(m2 log m) wherem⩽max(|V(T)|, |V(T′)|). Finally, we give an upper bound on the size of any intertwine of two given planar graphsHandH′. This bound is triply exponential inO(m5) wherem⩽max(|V(H)|, |V(H′)|). We introduce the concept ofl-length of a family of graphsL. We prove constructively that, if a minor closed familyLhas finitep-length and has obstructions of path-width at mostp, thenLhas a finite number of obstructions. Our proof gives a general upper bound, in termspand thep-length, on the size of any obstruction forL. 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 familyLand an appropriate integerl, an upper bound on thel-length ofLand applying one of the two general bounds.