# Upperbound for max degree of k-tree completion

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

• 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? Oct 9, 2020 at 2:53
• @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. Oct 9, 2020 at 3:53

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$$).
Note: I would not be surprised if you can get a better degree bound.. the additional $$\Delta$$ term feels unnecessary.
• 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. :) Oct 9, 2020 at 6:57