# A variant of tree or tree-cut decompositions

I am interested in the following variation of decomposing a graph into a tree. It is related to both the standard tree-decomposition of a graph and tree-cut decompositions.

Given a graph $G$, we want to find a tree $T$ and a partition $\{X_v \subseteq V(G): v \in V(T)\}$ of the vertices of $G$ indexed by the vertices of $T$, such that for all edges $xy \in E(G)$, either $x$ and $y$ are contained in the same set $X_v$, or there exists an edge $uv \in E(T)$ such that $x \in X_u$, $y \in X_v$. The width of the decomposition is the maximum size of $X_v$.

I remember having seen this type of decomposition analyzed in a paper, but I can no longer find a reference for the work. The specific question I'm interested in is the following.

Is it true that bounded treewidth and bounded degree suffice to force a bounded width decomposition of the above type?

Note that if the question holds, then it also implies that there exists a tree-decomposition of the graph such that every vertex is in a bounded number of bags, answering a question of Monkeymaths. To see this, assume $G$ has bounded degree and bounded treewidth, and assume that there exists a tree $T$ and partition $\{X_v: v \in V(T)\}$ as above. We may assume that $G$ is connected. It follows that the tree $T$ has bounded degree as well since for a $v \in V(T)$, every neighbor of $u$ of $v$ in $T$ must have a vertex $x \in X_u$ which is adjacent some vertex $y \in X_v$ by connectivity. To get the desired tree-decomposition of $G$, we subdivide each edge of $T$ to get a tree $T'$ and define $\{X'_v: v\in V(T')\}$ as follows. For $v \in V(T) \cap V(T')$, let $X'_v = X_v$. For edges $e = uv$, let $v_e$ be the vertex of $T'$ corresponding to the subdivided edge $e$. Define $X'_{v_e} = X_u \cup X_v$. Then $\{X'_v: v\in V(T')\}$ form the bags of a tree decomposition of bounded width. As the tree $T$ has bounded degree, every vertex of $G$ is in a bounded number of bags of $\{X'_v: v\in V(T')\}$, as desired.

I do not know whether if $G$ has bounded degree, bounded treewidth, and a bounded width tree-decomposition such that every vertex is in a bounded number of bags it follows that $G$ has the type of tree-partition decomposition of bounded width we defined above.

• Not sure if this is helpful, but I think this is equivalent to a question I have lately been thinking about a bit: Does every graph of bounded tree-width and bounded degree have a tree-decomposition of bounded width in which every vertex of G appears in a bounded number of parts? – monkeymaths May 26 '17 at 12:19
• I believe that a positive answer to my question would imply a positive answer to yours - I've edited the question to include a proof. Would a positive answer to your question imply the existence of the decomposition I'm looking for? – Paul Wollan May 29 '17 at 7:04
• I have sent you an email containing the argument I have in mind for the other implication (it's too long and possibly too distracting to post here). If it is correct, phrasing it in terms of tree-decompositions might make the question more accessible, although the structure you propose arguably has a simpler structure. I'm glad to see someone thinking about this. – monkeymaths May 29 '17 at 12:21