The structure and number of obstructions to treewidth.

*(English)*Zbl 0869.05060By 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.

Reviewer: H.Bodlaender (Utrecht)