Let $G(V,E)$ be an undirected graph with $|V|=n$ vertices. Let $tw(G)$ and $pw(G)$ represent the treewidth and pathwidth of $G$ respectively.
Let $H$ be a tree. Prove that $tw(H) = pw(H)$ if and only if $H$ is a caterpillar.
Let $J$ be a connected series-parallel graph. Characterize such graphs satisfying $tw(J) = pw(J)$.
Prove that for any graph $G$, $tw(G) \leq pw(G) \leq tw(G){\cdot}O({\log}n)$.
Construct a graph $F$ such that $pw(F) = tw(F){\cdot}O({\log}n)$.
Posted: Jun 06 '12
Seen: 35 times
Last updated: Jun 06 '12
