2
$\begingroup$

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$?

Improve this question
$\endgroup$
1
  • $\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$
    – Tom De Medts
    Commented Sep 6, 2016 at 9:29

1 Answer 1

Reset to default
4
$\begingroup$

Yes, an upperbound was proved in Upper Bounds on the Size of Obstructions and Intertwines by Lagergren. In case you cannot access the paper, 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 )$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .