<p>Your parameter "naive treewidth" is known as tree-partition-width in the literature.
It is known that if a graph has constant treewidth and constant maximum degree, then it has constant tree-partition-width. See [Wood 2009].</p>

<p>Note that your example in the update actually has pathwidth 2.</p>

<p>[Wood 2009] David R. Wood. On tree-partition-width. European Journal of Combinatorics 30 (2009) 1245-1253. <a href="https://doi.org/10.1016/j.ejc.2008.11.010" rel="noreferrer">https://doi.org/10.1016/j.ejc.2008.11.010</a>
(also on arXiv <a href="https://arxiv.org/abs/math/0602507" rel="noreferrer">https://arxiv.org/abs/math/0602507</a>)</p>

CC BY-SA 4.0
2019-03-20T16:08:33.463Z
Thanks a lot!
I thought that full binary tree with the path going through all leaves might provide a separation, but apparently that is not the case. Is there a simple tree-partition-width decomposition?
Artur Riazanov
CC BY-SA 4.0
2019-03-21T03:07:11.803Z
That's a good example.... I don't have a quick answer for it. We may read the proof in [Wood 2009] (or the references therein).
Yota Otachi
CC BY-SA 4.0
2019-03-20T15:19:42.363Z
2019-03-20T15:19:42.363Z
Yota Otachi
<p><a href="https://en.wikipedia.org/wiki/Treewidth" rel="nofollow noreferrer">Treewidth</a> has arguably pretty involved definition. Recently I was thinking about a problem and turns out it easy to solve it for graphs with small ``naive treewidth''. </p>

<p>Naive treewidth is defined as follows. Let <span class="math-container">$G=(V,E)$</span> be a graph. We say that <span class="math-container">$G$</span> has naive treewidth <span class="math-container">$k$</span> if there exists a partition <span class="math-container">$V_1 \sqcup V_2 \sqcup \ldots \sqcup V_m = V$</span> such that <span class="math-container">$|V_i| \le k$</span> and a tree <span class="math-container">$T = ([m], E_T)$</span> such that for every <span class="math-container">$(u,v) \in E$</span> either <span class="math-container">$u,v \in V_i$</span> for some <span class="math-container">$i \in [m]$</span> or <span class="math-container">$(u,v) \in V_i \times V_j$</span> such that <span class="math-container">$(i,j) \in E_T$</span>.</p>

<p>If <span class="math-container">$T$</span> is a path than we say that <span class="math-container">$G$</span> has naive pathwidth <span class="math-container">$k$</span>. </p>

<p>For naive pathwidth it is easy to see that it can be much larger than pathwidth. Consider a full binary tree with <span class="math-container">$2^k$</span> leaves. It has pathwidth <span class="math-container">$k-1$</span>. On the other hand notice that if naive pathwidth of a graph is <span class="math-container">$\le t$</span> than the partition contains at least <span class="math-container">${|V| \over t}$</span> blocks. Thus there exists a path in <span class="math-container">$G$</span> of length at least <span class="math-container">${|V| \over t} - 1$</span>. Since the longer path in the full binary tree of height <span class="math-container">$k$</span> is <span class="math-container">$2k$</span>, naive pathwidth of the full binary tree is at least <span class="math-container">${2^k \over 2k}$</span>. </p>

<p>Notice that instead of the full binary tree it was possible to use a tree with one vertex connected to the remaining <span class="math-container">$|V|-1$</span> vertices which gives even better separation. The reason I've used the binary tree is that for my purposes all graphs have constant degree. </p>

<p>My questions are:</p>

<ol>
<li>For a graph with small pathwidth (and constant degree if it is needed) can it be shown that it has small naive treewidth? If it is not true, how the counterexample looks like?</li>
<li>The same question for a graph with small treewidth.</li>
</ol>

<p><strong>Update:</strong> for arbitrary degrees there is a separation between treewidth and naive treewidth. The example is a path of length <span class="math-container">$n$</span> and a vertex connected to all vertices of the path. Treewidth of such graph is <span class="math-container">$2$</span> and naive treewidth is <span class="math-container">$\Omega(\sqrt{n})$</span>. The proof goes like this: consider the block <span class="math-container">$B$</span> containing the vertex of degree <span class="math-container">$n$</span>. Assume that this block contains at most <span class="math-container">$\sqrt{n} / 2$</span> vertices. Then there exists a path in <span class="math-container">$G - B$</span> containing at least <span class="math-container">$2 \sqrt{n}$</span>. Notice that in <span class="math-container">$T$</span> all the blocks should be connected to <span class="math-container">$B$</span>. Thus this path of length <span class="math-container">$2 \sqrt{n}$</span> must be contained in a single block. </p>

<graph-theory><treewidth>
Naive definition of treewidth
Artur Riazanov
# Naive definition of treewidth

(Asked by: username_0 on 2019-03-20)

[Treewidth](https://en.wikipedia.org/wiki/Treewidth) has arguably pretty involved definition. Recently I was thinking about a problem and turns out it easy to solve it for graphs with small ``naive treewidth''.

Naive treewidth is defined as follows. Let $G=(V,E)$ be a graph. We say that $G$ has naive treewidth $k$ if there exists a partition $V\_1 \sqcup V\_2 \sqcup \ldots \sqcup V\_m = V$ such that $|V\_i| \le k$ and a tree $T = ([m], E\_T)$ such that for every $(u,v) \in E$ either $u,v \in V\_i$ for some $i \in [m]$ or $(u,v) \in V\_i \times V\_j$ such that $(i,j) \in E\_T$.

If $T$ is a path than we say that $G$ has naive pathwidth $k$.

For naive pathwidth it is easy to see that it can be much larger than pathwidth. Consider a full binary tree with $2^k$ leaves. It has pathwidth $k-1$. On the other hand notice that if naive pathwidth of a graph is $\le t$ than the partition contains at least ${|V| \over t}$ blocks. Thus there exists a path in $G$ of length at least ${|V| \over t} - 1$. Since the longer path in the full binary tree of height $k$ is $2k$, naive pathwidth of the full binary tree is at least ${2^k \over 2k}$.

Notice that instead of the full binary tree it was possible to use a tree with one vertex connected to the remaining $|V|-1$ vertices which gives even better separation. The reason I've used the binary tree is that for my purposes all graphs have constant degree.

My questions are:

1. For a graph with small pathwidth (and constant degree if it is needed) can it be shown that it has small naive treewidth? If it is not true, how the counterexample looks like?
2. The same question for a graph with small treewidth.

**Update:** for arbitrary degrees there is a separation between treewidth and naive treewidth. The example is a path of length $n$ and a vertex connected to all vertices of the path. Treewidth of such graph is $2$ and naive treewidth is $\Omega(\sqrt{n})$. The proof goes like this: consider the block $B$ containing the vertex of degree $n$. Assume that this block contains at most $\sqrt{n} / 2$ vertices. Then there exists a path in $G - B$ containing at least $2 \sqrt{n}$. Notice that in $T$ all the blocks should be connected to $B$. Thus this path of length $2 \sqrt{n}$ must be contained in a single block.

**Tags:** graph-theory, treewidth

---

## 1 answers

### Answer by username_1 on 2019-03-20. Score: 9 | Accepted answer

Your parameter "naive treewidth" is known as tree-partition-width in the literature.
It is known that if a graph has constant treewidth and constant maximum degree, then it has constant tree-partition-width. See [Wood 2009].

Note that your example in the update actually has pathwidth 2.

[Wood 2009] David R. Wood. On tree-partition-width. European Journal of Combinatorics 30 (2009) 1245-1253. <https://doi.org/10.1016/j.ejc.2008.11.010>
(also on arXiv <https://arxiv.org/abs/math/0602507>)

> **Comments:**
> **username_0**: Thanks a lot! I thought that full binary tree with the path going through all leaves might provide a separation, but apparently that is not the case. Is there a simple tree-partition-width decomposition?  
> **username_1**: That's a good example.... I don't have a quick answer for it. We may read the proof in [Wood 2009] (or the references therein).  

---

