Suggest a Book

# Graphs with treewidth equal to pathwidth

Level: unknown

posted Jun 06 '12

Shiva Kintali
691 1 6 21
http://www.cs.princeton.e...

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.

1. Let $H$ be a tree. Prove that $tw(H) = pw(H)$ if and only if $H$ is a caterpillar.

2. Let $J$ be a connected series-parallel graph. Characterize such graphs satisfying $tw(J) = pw(J)$.

3. Prove that for any graph $G$, $tw(G) \leq pw(G) \leq tw(G){\cdot}O({\log}n)$.

4. Construct a graph $F$ such that $pw(F) = tw(F){\cdot}O({\log}n)$.

delete retag edit

## Stats

Posted: Jun 06 '12

Seen: 35 times

Last updated: Jun 06 '12