Mrthdrb

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$ blocks. Thus there exists a path in $G$ of length at least $V - 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(sqrtn)$. The proof goes like this: consider the block $B$ containing the vertex of degree $n$. Assume that this block contains at most $sqrtn / 2$ vertices. Then there exists a path in $G - B$ containing at least $2 sqrtn$. Notice that in $T$ all the blocks should be connected to $B$. Thus this path of length $2 sqrtn$ must be contained in a single block.

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)