patternMinor
treewidth of a given graph
Viewed 0 times
treewidthgivengraph
Problem
Is the treewidth of this graph equal to 2?
I have tried to prove it through the definition of a tree decomposition.
If its not correct can someone give any hints?
I have tried to prove it through the definition of a tree decomposition.
If its not correct can someone give any hints?
Solution
In the survey Treewidth, partial $k$-trees, and chordal graphs by Pinar Heggernes, we have the following lemma, whose proof is given as an exercise.
Lemma. Let $(\{X_i \mid i \in I\}, T = (I, M))$ be a tree decomposition of $G = (V, E)$, and let $K \subseteq V$ be a clique in $G$. Then there exists an $i \in I$ with $K \subseteq X_i$.
Prove this lemma, and conclude that, as Yuval answered,
Corollary. For every graph $G$, $tw(G) \geq \omega(G) - 1$.
Conclude that the treewidth is at least three.
The treewidth happens to be at most three as well, but that's a different exercise.
Lemma. Let $(\{X_i \mid i \in I\}, T = (I, M))$ be a tree decomposition of $G = (V, E)$, and let $K \subseteq V$ be a clique in $G$. Then there exists an $i \in I$ with $K \subseteq X_i$.
Prove this lemma, and conclude that, as Yuval answered,
Corollary. For every graph $G$, $tw(G) \geq \omega(G) - 1$.
Conclude that the treewidth is at least three.
The treewidth happens to be at most three as well, but that's a different exercise.
Context
StackExchange Computer Science Q#105166, answer score: 3
Revisions (0)
No revisions yet.