For any $k$, the class of graphs of treewidth at most $k$ can be characterized by a finite set of forbidden minors.

For treewidth $1$ and $2$, the set is of size $1$. Then for treewidth $3$, the set is of size $4$, and beyond that the size of the set grows very rapidly.

For a given $k$, is there a known upper bound on the number of vertices for the forbidden minors for treewidth at most $k$?

  • $\begingroup$ Wikipedia says "For larger values of $k$, the number of forbidden minors grows at least as quickly as the exponential of the square root of $k$.[9] However, known upper bounds on the size and number of forbidden minors are much higher than this lower bound.[10]". (en.wikipedia.org/wiki/…) Have you checked this reference? $\endgroup$ Sep 6 '16 at 9:29

Yes, an upperbound was proved in Upper Bounds on the Size of Obstructions and Intertwines by Lagergren. The paper is behind a paywall, but the relevant theorem is Theorem 5.9.

If $G$ is an obstruction for graphs of tree-width at most $k$, then $|E(G)|$ is at most doubly exponential in $O(k^5) $.

In the same paper, Lagergren also bounds the size of a forbidden minor for path-width at most $p$.

If $G$ is an obstruction for graphs of path-width at most $p$, then $|E(G)|$ is at most exponential in $O( p^4 )$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.