Upper bounds on the size of obstructions and intertwines (Q1272647)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Upper bounds on the size of obstructions and intertwines |
scientific article |
Statements
Upper bounds on the size of obstructions and intertwines (English)
0 references
22 June 1999
0 references
An upper bound is given in \(p^4\) on the size of any obstruction for path-width at most \(p\), and a doubly exponential upper bound in \(k^5\) on the size of any obstruction for tree-width at most \(k\). Further results are given that lead on to a constructive proof that, if a minor closed family \(L\) has finite \(p\)-length and has obstruction of path-width at most \(p\), then \(L\) has a finite number of obstructions. Further upper bounds are also obtained.
0 references
upper bound
0 references
path-width
0 references
obstruction
0 references
tree-width
0 references