For a problem that I'm working on, it would be very convenient if the following two properties were true:
- If a graph has treewidth $k$, then after subdividing any edge, the graph still has treewidth $k$.
- 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:
- 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:
- Subdividing an edge is a special case of splitting a vertex.
- 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.