<p>It is known that a graph of treewidth <span class="math-container">$k$</span> and maximum degree <span class="math-container">$\Delta$</span> has tree partition width at most <span class="math-container">$O(k\Delta)$</span>. See <a href="https://arxiv.org/abs/math/0602507" rel="noreferrer">Wood, arXiv:math/0602507</a>.</p>
<p>From a tree partition of width <span class="math-container">$O(k\Delta)$</span> a triangulation of width <span class="math-container">$O(k\Delta)$</span> and maximum degree <span class="math-container">$O(k\Delta^2)$</span> follows pretty directly (start with the tree partition, make every bag into a clique, make every vertex <span class="math-container">$v$</span> in <span class="math-container">$U$</span> adjacent to all vertices in all bags appearing together with neighbors of <span class="math-container">$v$</span>).</p>
<p>So you get a (minimal) triangulation with the bounds above.</p>
<p>Note: I would not be surprised if you can get a better degree bound.. the additional <span class="math-container">$\Delta$</span> term feels unnecessary.</p>

CC BY-SA 4.0
2020-10-09T06:47:57.433Z
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.
daniello
CC BY-SA 4.0
2020-10-09T06:53:13.600Z
Yeah, a trangulation (a.k.a. chordal completion) is good enough for the purpose. Thanks.
Cyriac Antony
CC BY-SA 4.0
2020-10-09T06:57:09.757Z
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. :)
Cyriac Antony
CC BY-SA 4.0
2020-10-09T06:46:46.770Z
2020-10-09T06:52:54.687Z
2020-10-09T06:52:54.687Z
daniello
<p><em>Definitions</em>: For a graph <span class="math-container">$G$</span>, a <span class="math-container">$k$</span>-tree completion of <span class="math-container">$G$</span> is a <a href="https://en.wikipedia.org/wiki/K-tree" rel="noreferrer"><span class="math-container">$k$</span>-tree</a> obtained by adding edges to <span class="math-container">$G$</span> (if <span class="math-container">$G$</span> has a <span class="math-container">$k$</span>-tree completion, <span class="math-container">$G$</span> is said to be a <a href="https://en.wikipedia.org/wiki/Partial_k-tree#CITEREFArnborgProskurowski1989" rel="noreferrer">partial <span class="math-container">$k$</span>-tree</a>). The least integer <span class="math-container">$k$</span> such that <span class="math-container">$G$</span> has a <span class="math-container">$k$</span>-tree completion is called the treewidth of <span class="math-container">$G$</span>. The maximum degree of a graph <span class="math-container">$G$</span> is denoted by <span class="math-container">$\Delta(G)$</span>.</p>
<p><em>Question</em>: Suppose that <span class="math-container">$G$</span> has a <span class="math-container">$k$</span>-tree completion.<br />
<strong>Is there an upper bound <span class="math-container">$U$</span> in terms of <span class="math-container">$k$</span> and <span class="math-container">$\Delta(G)$</span> such that<br />
there exist a <span class="math-container">$k$</span>-tree completion <span class="math-container">$G'$</span> of <span class="math-container">$G$</span> with <span class="math-container">$\Delta(G')\leq U\,?$</span></strong><br />
(note: To be explicit, <span class="math-container">$U$</span> is a function of <span class="math-container">$k$</span> and <span class="math-container">$\Delta(G)$</span> )</p>
<p><em>Context</em>: I have a graph parameter <span class="math-container">$x(G)$</span> such that <span class="math-container">$x(G)\leq \Delta(G)+p$</span> for every chordal graph <span class="math-container">$G$</span> where <span class="math-container">$p$</span> is a constant. Using this result, I am trying to give an upper bound for <span class="math-container">$x(G)$</span> in general graphs in terms of treewidth of <span class="math-container">$G$</span> and <span class="math-container">$\Delta(G)$</span>.</p>

CC BY-SA 4.0
2020-10-09T02:53:20.710Z
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?
daniello
CC BY-SA 4.0
2020-10-09T03:53:28.583Z
@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.
Cyriac Antony
<graph-theory>
Upperbound for max degree of k-tree completion
Cyriac Antony
# Upperbound for max degree of k-tree completion

(Asked by: username_0 on 2020-10-08)

*Definitions*: For a graph $G$, a $k$-tree completion of $G$ is a [$k$-tree](https://en.wikipedia.org/wiki/K-tree) obtained by adding edges to $G$ (if $G$ has a $k$-tree completion, $G$ is said to be a [partial $k$-tree](https://en.wikipedia.org/wiki/Partial_k-tree#CITEREFArnborgProskurowski1989)). 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)$.

**Tags:** graph-theory

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1 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.  

---

## 1 answers

### Answer by username_1 on 2020-10-09. Score: 5 | Accepted answer

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](https://arxiv.org/abs/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.

> **Comments:**
> **username_1**: 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.  
> **username_0**: Yeah, a trangulation (a.k.a. chordal completion) is good enough for the purpose. Thanks.  
> **username_0**: 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. :)  

---

