Is it true that $\Delta(G)\leq3$ implies $TW(G)\leq6$? (where $TW$ is the "treewidth"). I know that for $\Delta(G)\leq4$ there is no bound for treewidth because the $n\times n$ grid has $TW=n$. For $\Delta\leq2$ it is easy to see that $TW\leq 2$, and the case $\Delta\leq1$ is trivial. I think this is the right bound only because I cannot find bigger counterexamples; but I dont have any idea to prove this.
2026-04-05 17:26:34.1775409994
On
Exists a bound for threewidth in $\Delta(G)\leq 3$ graphs?
35 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
0
On
A simple proof goes this way:
Take $K_n$ the complete graph in $n$ vertices. Take $v\in G$, replace it with a cycle of length $d(v)=n-1$ and connect the $d(v)$ vertices in a 1-to-1 fashion to a vertex of the cycle. The result is that every vertex in the cycle has degree $3$. Repeat this until no vertex of degree $>3$ left. The graph $G$ obtained is $3$-regular and (clearly) $K_n\leq G$. Then, $\text{TW}(G)\geq\text{TW}(K_n)=n-1$. So, the treewidth is unbounded even in the class of $3$-regular graphs.