<p>Answering my own question: the answer is "no". For each <span class="math-container">$k \ge 3$</span>, Ding and Oporowski construct a graph <span class="math-container">$G_k$</span> on <span class="math-container">$2k$</span> vertices with treewidth <span class="math-container">$3$</span>, such that in every optimal tree decomposition of <span class="math-container">$G_k$</span> there is a vertex which is in at least <span class="math-container">$2k-2$</span> bags (see Figure 1 in their paper).</p>

<p><em>Ding, Guoli; Oporowski, Bogdan</em>, <a href="http://dx.doi.org/10.1002/jgt.3190200412" rel="noreferrer"><strong>Some results on tree decomposition of graphs</strong></a>, J. Graph Theory 20, No. 4, 481-499 (1995). <a href="https://zbmath.org/?q=an:0837.05044" rel="noreferrer">ZBL0837.05044</a>.</p>

CC BY-SA 4.0
2020-06-04T21:20:15.837Z
2020-06-04T21:20:15.837Z
hdur
<p>Let <span class="math-container">$G$</span> be a graph on <span class="math-container">$n$</span> vertices whose maximum degree is at most <span class="math-container">$\Delta$</span> and whose treewidth is at most <span class="math-container">$k$</span>.
Does there exist a function <span class="math-container">$f(k, \Delta)$</span>, independent of <span class="math-container">$n$</span>, such that it is possible to find a tree decomposition of <span class="math-container">$G$</span> of width <span class="math-container">$k$</span> (i.e. with bags of size <span class="math-container">$k+1$</span>) with the additional property that every vertex of <span class="math-container">$G$</span> is in at most <span class="math-container">$f(k, \Delta)$</span> of the bags?</p>

<p>A related concept which is perhaps relevant is that of <em>domino treewidth</em>.
We say a tree decomposition is <em>domino</em> if every vertex is in at most <span class="math-container">$2$</span> of the bags.
Bodlaender and Engelfriet [ <a href="https://link.springer.com/chapter/10.1007/3-540-59071-4_33" rel="noreferrer">https://link.springer.com/chapter/10.1007/3-540-59071-4_33</a> ] show that there exists <span class="math-container">$c(k, \Delta)$</span> such that every graph with maximum degree at most <span class="math-container">$\Delta$</span> and treewidth at most <span class="math-container">$k$</span> has a domino tree decomposition of width <span class="math-container">$c(k, \Delta)$</span>.</p>

<p>Thus, by increasing the size of the bags from <span class="math-container">$k$</span> to <span class="math-container">$c(k, \Delta)$</span>, they can find a new tree decomposition where each vertex is in at most <span class="math-container">$2$</span> bags (and clearly the <span class="math-container">$2$</span> cannot be lowered).
It seems to me that there is a trade-off between "size of the bags" and "number of bags per vertex" for the class of graphs with bounded degree and treewidth, and my question is if it possible to control the number of "bags per vertex" if we insist on not increasing the bag size.</p>

CC BY-SA 4.0
2020-05-20T12:01:42.963Z
I have no formal proof but it seems already hard to do for the n-cycle. Have you tried this direction?
holf
CC BY-SA 4.0
2020-05-20T12:10:54.220Z
I know how to find an optimal tree decomposition for the $n$-cycle where each vertex is at most in $3$ bags. Say $n = 2k$ (the odd case is similar) and label the vertices of an $n$-cycle by $v_1 v_2 \dotsb v_{2k}$. Then the sets

$\{ v_1 v_2 v_{2k} \}$, $\{ v_2, v_{2k} v_{2k-1} \}$, $\{ v_2 v_3 v_{2k-1} \}$, $\{ v_3 v_{2k-1} v_{2k-2} \}$, ..., $\{ v_j, v_{j+1} v_{2k+1-j} \}$, $\{ v_{j+1} v_{2k+1-j} v_{2k-j} \}$, ...

form the bags of a tree decomposition of width $2$ (where the underlying tree is a path).
hdur
CC BY-SA 4.0
2020-05-20T14:05:14.897Z
How about Halin graphs?
Yota Otachi
CC BY-SA 4.0
2020-05-22T09:06:53.073Z
@YotaOtachi Thanks for the suggestion. I checked a proof by Bodlaender [ https://web.archive.org/web/20040728112030/http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1988/1988-14.pdf ] where he constructs tree decompositions of width 3 for Halin graphs, and I verified his tree decomposition does_not_ have a bounded number of bags per vertex. Of course this still does not show that the answer to my question is "no" but it seems like an interesting subcase to keep on looking.
hdur
<graph-theory><treewidth>
Tree decompositions of optimal width where every vertex is in a bounded number of bags?
hdur
# Tree decompositions of optimal width where every vertex is in a bounded number of bags?

(Asked by: username_0 on 2020-05-20)

Let $G$ be a graph on $n$ vertices whose maximum degree is at most $\Delta$ and whose treewidth is at most $k$.
Does there exist a function $f(k, \Delta)$, independent of $n$, such that it is possible to find a tree decomposition of $G$ of width $k$ (i.e. with bags of size $k+1$) with the additional property that every vertex of $G$ is in at most $f(k, \Delta)$ of the bags?

A related concept which is perhaps relevant is that of *domino treewidth*.
We say a tree decomposition is *domino* if every vertex is in at most $2$ of the bags.
Bodlaender and Engelfriet [ <https://link.springer.com/chapter/10.1007/3-540-59071-4_33> ] show that there exists $c(k, \Delta)$ such that every graph with maximum degree at most $\Delta$ and treewidth at most $k$ has a domino tree decomposition of width $c(k, \Delta)$.

Thus, by increasing the size of the bags from $k$ to $c(k, \Delta)$, they can find a new tree decomposition where each vertex is in at most $2$ bags (and clearly the $2$ cannot be lowered).
It seems to me that there is a trade-off between "size of the bags" and "number of bags per vertex" for the class of graphs with bounded degree and treewidth, and my question is if it possible to control the number of "bags per vertex" if we insist on not increasing the bag size.

**Tags:** graph-theory, treewidth

> **Comments:**
> **username_1**: I have no formal proof but it seems already hard to do for the n-cycle. Have you tried this direction?  
> **username_0**: I know how to find an optimal tree decomposition for the $n$-cycle where each vertex is at most in $3$ bags. Say $n = 2k$ (the odd case is similar) and label the vertices of an $n$-cycle by $v_1 v_2 \dotsb v_{2k}$. Then the sets  $\{ v_1 v_2 v_{2k} \}$, $\{ v_2, v_{2k} v_{2k-1} \}$, $\{ v_2 v_3 v_{2k-1} \}$, $\{ v_3 v_{2k-1} v_{2k-2} \}$, ..., $\{ v_j, v_{j+1} v_{2k+1-j} \}$, $\{ v_{j+1} v_{2k+1-j} v_{2k-j} \}$, ...  form the bags of a tree decomposition of width $2$ (where the underlying tree is a path).  
> **username_2**: How about Halin graphs?  
> **username_0**: @YotaOtachi Thanks for the suggestion. I checked a proof by Bodlaender [ https://web.archive.org/web/20040728112030/http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1988/1988-14.pdf ] where he constructs tree decompositions of width 3 for Halin graphs, and I verified his tree decomposition does_not_ have a bounded number of bags per vertex. Of course this still does not show that the answer to my question is "no" but it seems like an interesting subcase to keep on looking.  

---

## 1 answers

### Answer by username_0 on 2020-06-04. Score: 6 | Accepted answer

Answering my own question: the answer is "no". For each $k \ge 3$, Ding and Oporowski construct a graph $G\_k$ on $2k$ vertices with treewidth $3$, such that in every optimal tree decomposition of $G\_k$ there is a vertex which is in at least $2k-2$ bags (see Figure 1 in their paper).

*Ding, Guoli; Oporowski, Bogdan*, [**Some results on tree decomposition of graphs**](http://dx.doi.org/10.1002/jgt.3190200412), J. Graph Theory 20, No. 4, 481-499 (1995). [ZBL0837.05044](https://zbmath.org/?q=an:0837.05044).


---

