zbMATH — the first resource for mathematics

The structure and number of obstructions to treewidth. (English) Zbl 0869.05060
By the graph minor theory of Robertson and Seymour, every class of graphs that is closed under taking minors has a characterization in terms of a finite obstruction set. This paper looks to what obstruction set of graphs of treewidth \(\leq k\) graphs of size \(k+3\) belong. The paper starts with showing that for non-complete graphs \(G\), the minimum over all edges of the larger degree of the endpoints of the edges is a lower bound for the treewidth of \(G\). The result then is used to characterize all graphs of \(k+3\) vertices that belong to the obstruction set of graphs of treewidth at most \(k\); both in terms of a structural characterization, and a canonical representation, that can be used to enumerate them. Also, formulas for the number of such obstructions are given.

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
05C35 Extremal problems in graph theory
05C75 Structural characterization of families of graphs
Full Text: DOI