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
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    upper bound
    0 references
    path-width
    0 references
    obstruction
    0 references
    tree-width
    0 references
    0 references
    0 references