Exercises Videos Notes Multiple-choice questions Apps

Related books

Matching Theory Graph Coloring Problems Chromatic Graph Theory Introduction to Graph Theory Suggest a Book
2

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:
Printable version LaTeX source
delete flag offensive retag edit

updated Aug 14 '12

diego gravatar image diego flag of Argentina
71 7
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