1. Contraction obstructions for treewidth
- Author
-
Fomin, Fedor V., Golovach, Petr, and Thilikos, Dimitrios M.
- Subjects
- *
GRAPH theory , *ALGORITHMS , *TREE graphs , *CONTRACTIONS (Topology) , *MATHEMATICAL analysis , *TOPOLOGY - Abstract
Abstract: We provide two parameterized graphs , with the following property: for every positive integer k, there is a constant such that every graph G with treewidth at least , contains one of , , as a contraction, where is a complete graph on k vertices. These three parameterized graphs can be seen as “obstruction patterns” for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF