Exists a bound for threewidth in $\Delta(G)\leq 3$ graphs?

35 Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

As part of their work on graph minors leading to the Robertson–Seymour theorem and the graph structure theorem, Neil Robertson and Paul Seymour proved that a family $F$ of finite graphs has unbounded treewidth if and only if the minors of graphs in $F$ include arbitrarily large square grid graphs, or equivalently subgraphs of the hexagonal tiling formed by intersecting it with arbitrarily large disks. (Wikipedia)

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.