Definitions: For a graph $G$, a $k$-tree completion of $G$ is a $k$-tree obtained by adding edges to $G$ (if $G$ has a $k$-tree completion, $G$ is said to be a partial $k$-tree). The least integer $k$ such that $G$ has a $k$-tree completion is called the treewidth of $G$. The maximum degree of a graph $G$ is denoted by $\Delta(G)$.

Question: Suppose that $G$ has a $k$-tree completion.
Is there an upper bound $U$ in terms of $k$ and $\Delta(G)$ such that
there exist a $k$-tree completion $G'$ of $G$ with $\Delta(G')\leq U\,?$

(note: To be explicit, $U$ is a function of $k$ and $\Delta(G)$ )

Context: I have a graph parameter $x(G)$ such that $x(G)\leq \Delta(G)+p$ for every chordal graph $G$ where $p$ is a constant. Using this result, I am trying to give an upper bound for $x(G)$ in general graphs in terms of treewidth of $G$ and $\Delta(G)$.

  • $\begingroup$ So do you care that the completion is a k-tree completion and not a k’-tree completion for a k’ which is a function of the treewidth k and max degree of G? $\endgroup$
    – daniello
    Oct 9, 2020 at 2:53
  • $\begingroup$ @daniello Not really. It is perfectly fine if it is a k'-tree completion where k' is a function of treewidth k of G and max degree of G. $\endgroup$ Oct 9, 2020 at 3:53

1 Answer 1


It is known that a graph of treewidth $k$ and maximum degree $\Delta$ has tree partition width at most $O(k\Delta)$. See Wood, arXiv:math/0602507.

From a tree partition of width $O(k\Delta)$ a triangulation of width $O(k\Delta)$ and maximum degree $O(k\Delta^2)$ follows pretty directly (start with the tree partition, make every bag into a clique, make every vertex $v$ in $U$ adjacent to all vertices in all bags appearing together with neighbors of $v$).

So you get a (minimal) triangulation with the bounds above.

Note: I would not be surprised if you can get a better degree bound.. the additional $\Delta$ term feels unnecessary.

  • $\begingroup$ Note: You ask for a k’-tree completion, this answer gives a triangulation. From your comments my guess is that a triangulation of width k’ is good enough for you. If not, you can probably still get a k’-tree completion with some additional massaging on top of this. $\endgroup$
    – daniello
    Oct 9, 2020 at 6:47
  • $\begingroup$ Yeah, a trangulation (a.k.a. chordal completion) is good enough for the purpose. Thanks. $\endgroup$ Oct 9, 2020 at 6:53
  • $\begingroup$ It's rather unfortunate that the bound involves $\Delta^2$. For the parameter $x(G)$ I am dealing with, it is known that $x(G)\leq \Delta(G)^2+1$ for every graph. :) $\endgroup$ Oct 9, 2020 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.