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.

  • 1
    $\begingroup$ 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? $\endgroup$ – monkeymaths May 26 '17 at 12:19
  • $\begingroup$ 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? $\endgroup$ – Paul Wollan May 29 '17 at 7:04
  • $\begingroup$ 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. $\endgroup$ – monkeymaths May 29 '17 at 12:21

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... :)


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.