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.

  • $\begingroup$ I have no formal proof but it seems already hard to do for the n-cycle. Have you tried this direction? $\endgroup$ – holf May 20 '20 at 12:01
  • 2
    $\begingroup$ 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). $\endgroup$ – hdur May 20 '20 at 12:10
  • $\begingroup$ How about Halin graphs? $\endgroup$ – Yota Otachi May 20 '20 at 14:05
  • 2
    $\begingroup$ @YotaOtachi Thanks for the suggestion. I checked a proof by Bodlaender [ web.archive.org/web/20040728112030/http://archive.cs.uu.nl/pub/… ] 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. $\endgroup$ – hdur May 22 '20 at 9:06

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, J. Graph Theory 20, No. 4, 481-499 (1995). ZBL0837.05044.


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.