5
$\begingroup$

It is a well-known fact that for any minor H of a graph G (commonly written as $H \leq_m G$), the treewidth of H is smaller than or equal to that of G.

Minors of a graph are created through the operations of (1) vertex deletion, (2) edge deletion and (3) edge contraction. I am curious as to whether one can bound the decrease in treewidth when applying any single operation from (1)-(3). Of particular interest for me is the question whether said decrease can always be bounded by some constant.

$\endgroup$
4
$\begingroup$

The decrease in tree width of any of the three operations will be 0 or 1. The proof is simple (I will take the case of the vertex deletion).

Let $G$ be the original graph and $G' = G - v$ be the graph obtained by deleting $v$.

Let $T'$ be an optimal tree decomposition of $G'$, with $\text{tw}(G') = w'$.

Now, construct $T$ from $T'$ by adding $v$ to every bag of $T'$. Clearly, $T$ is a tree decomposition for $G$ with width $\text{tw}(G) \leq \text{tw}(T) = 1 + \text{tw}(G') = 1 + w'$.

$\endgroup$
  • 1
    $\begingroup$ Indeed, it seems trivial now. Thank you. $\endgroup$ – SmeltQuake Feb 17 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.