For a problem that I'm working on, it would be very convenient if the following two properties were true:

  1. If a graph has treewidth $k$, then after subdividing any edge, the graph still has treewidth $k$.
  2. If a (connected, nontrivial) graph has treewidth $k$, then performing the following operation gives a graph with treewidth at most $k + 1$: pick any subset of the graph's vertices; for each vertex $v$ in the subset, replace $v$ with a triangle graph on new vertices $\{v_1, v_2, v_3\}$, and replace each edge $\{u, v\}$ with one new edge $\{u, v_1\}$, $\{u, v_2\}$, or $\{u, v_3\}$ of your choice. (This is a generalization of the replacement product with a triangle graph.)

Wikipedia says the following about treewidth:

Intuitively, a huge graph $G$ has small tree width if and only if $G$ takes the structure of a huge tree whose nodes and edges have been replaced by small graphs.

It makes sense to me, then, that these properties would preserve bounded treewidth, but I'm having a hard time proving them from the definition of treewidth in terms of trees of bags.

The first operation, I'm virtually certain preserves treewidth. (I can't find a reference for it, but this question mentions it.) It is intuitive to me that the second operation should not increase the treewidth by much, but I'm less sure that this is the case for every graph and every possible replacement.

Edit: I'm going to throw a third possible theorem on the pile:

  1. If a graph has treewidth $k$, then after splitting any vertex, the graph still has treewidth $k$. By splitting a vertex, I mean the inverse operation of edge contraction: replacing a vertex $v$ with two new vertices $\{v_1, v_2\}$, adding an edge between $v_1$ and $v_2$, and replacing each edge $\{u, v\}$ with one new edge $\{u, v_1\}$ or $\{u, v_2\}$ of your choice.

If this is true, it easily implies the other two:

  1. Subdividing an edge is a special case of splitting a vertex.
  2. We can reproduce the vertex-to-triangle operation on a graph of treewidth $k$ as follows. For each vertex $v_1$ in the subset of vertices being converted to triangles, subdivide $v_1$ twice, apportioning the existing edges to $v_1$ appropriately to get our three vertices $v_1, v_2, v_3$. This graph still has treewidth $k$, and is identical to our desired graph except for missing an edge between each $v_2, v_3$ pair. Add a new vertex $w$ that is adjacent to all $v_2$ and $v_3$ vertices; this at most increases the treewidth to $k + 1$. Now subdivide $w$ a bunch of times, then take a minor to get the desired graph without increasing the treewidth.

Number 1 is true. Proof from here: If the original graph is a tree, then the graph with any edge subdivided is also a tree, so it still has treewidth 1. Otherwise, suppose we are splitting the edge $\{u,v\}$ with a new vertex $w$. Find a bag that contains both $u$ and $v$ and attach a new bag $\{u,v,w\}$.

Number 3 is false. Assume that you could in fact split any vertex in a graph without increasing the graph's treewidth.

  1. Let the original graph be the disjoint union of $k$ path graphs $G_0, \dots, G_{k-1}$, each of length $k$. This graph has treewidth 1.
  2. Add a new vertex connected to all of the existing vertices. This increases the treewidth to 2.
  3. Subdivide the new vertex repeatedly to form a balanced binary tree connecting all of the vertices in the original graph. Using our hypothesis, this graph still has treewidth 2.
  4. Take a minor of this graph to get a graph in which every other pair $(G_{2i}, G_{2i + 1})$ of adjacent path graphs has an edge between each corresponding vertex. As a minor of the previous graph, this graph should still have treewidth at most 2.
  5. Repeat steps 2–4 again to connect the other pairs of adjacent path graphs $(G_{2i + 1}, G_{2i + 2})$, giving us a grid graph and increasing the treewidth to at most 3.
  6. Now we have shown that a $k \times k$ grid graph has treewidth at most 3, contradicting the known theorem that a $k \times k$ grid graph has treewidth $k$.

Number 2 is false by a similar argument to number 3. The simultaneous vertex-to-triangle operation would allow you to build a balanced binary tree joining all of the vertices of a $k \times k$ grid graph using $O(\log k)$ operations, and conclude from that that the $k \times k$ grid graph has treewidth $O(\log k)$.


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.