Given a graph $G$, we define $\mathrm{la}(G)$ as the smallest $r$ such that $G$ is a minor of some $T\times K_r$, where $T$ is a tree (and $\times$ in this context is the cartesian product).
Prove that the treewidth of $G$ is bounded in between $\mathrm{la}(G)-1$ and $\mathrm{la}(G)$.
Show that the bounds are sharp (hint: use $G=Q_3$, the 3-cube graph).
Posted: Aug 13 '12
Seen: 116 times
Last updated: Aug 14 '12
Recognizing series-parallel graphs in linear time
Treewidth and feedback vertex set