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.



A variant of tree or tree-cut decompositions
I mentioned your type of decomposition to my colleague Konstantinos and he pointed out that it had appeared in the literature under the name "strong tree-decomposition"! D. Seese introduced it in 1985 ('Tree-partite graphs and the complexity of algorithms'). Bodlaender and Engelfriet then picked it up in 1994 in an article entitled 'Domino Treewidth'. Corollary 13 in their paper states that if tree-width and maximum degree are bounded, then so is the strong tree-width.


This also answers my question positively. A question that I had in fact discussed with Konstantinos on several occasions... :)


