Upper bounds on the size of obstructions and intertwines
type: Item
instance of: scholarly article
title: Upper bounds on the size of obstructions and intertwines
zbMATH Open document ID: 0915.05070
author: Jens Lagergren
published in: Journal of Combinatorial Theory. Series B
publication date: 1999-06-22T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1234728
zbMATH Keywords: upper bound
zbMATH Keywords: path-width
zbMATH Keywords: obstruction
zbMATH Keywords: tree-width
reviewed by: Chris Jagger
MaRDI profile type: Publication
OpenAlex ID: W2060945907
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Easy problems for tree-decomposable graphs
cites work: Quickly excluding a forest
cites work: Solution to König's Graph Embedding Problem
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Q5682013
cites work: Quickly excluding a planar graph
cites work: Graph minors. XX: Wagner's conjecture
cites work: Graph minors. XIII: The disjoint paths problem
cites work: A Menger-like property of tree-width: The finite case
DOI: 10.1006/JCTB.1997.1788
description: scientific article; zbMATH DE number 1234728