Upper bounds on the size of obstructions and intertwines (Q1272647)

From MaRDI portal





scientific article; zbMATH DE number 1234728
Language Label Description Also known as
English
Upper bounds on the size of obstructions and intertwines
scientific article; zbMATH DE number 1234728

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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references