Contraction obstructions for treewidth

AbstractWe provide two parameterized graphs Γk, Πk with the following property: for every positive integer k, there is a constant ck such that every graph G with treewidth at least ck, contains one of Kk, Γk, Πk as a contraction, where Kk 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