Suggest a Book

# Treewidth, the natural way

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).

Level:
delete retag edit

POST AN EXERCISE POST A VIDEO POST NOTES POST MULTIPLE-CHOICE QUESTION

## Stats

Posted: Aug 13 '12

Seen: 116 times

Last updated: Aug 14 '12