Consider a $k$ regular graph of $n$ vertices, where $3 \leq k \leq (n-1)$. Is there any upper or lower bound, in the worst case, known for either the tree-width or the clique width of each $k$ regular family?



Tree width and clique width of regular graphs
For each $k$-regular family, the treewidth and cliquewidth can be both $\Theta(n)$, due to the existence of expanders.


By [On Balanced Separators, Treewidth, and Cycle Rank](https://arxiv.org/abs/1012.1344) Thm. 2.1, $tw(G) \geq \tilde s(G) -1$, and by the definition of the strict balanced separator number, $\tilde s(G)$ is at least the size of a balanced separator of a graph. A random regular graph is an expander, which in turn makes the size of balanced separators $\Theta(n)$. Thus $tw(G)=\Theta(n)$.


By [The Tree-Width of Clique-Width Bounded Graphs without $K\_{n,n}$](https://link.springer.com/chapter/10.1007/3-540-40064-8_19), every graph of clique-width $k$ which does not
contain the complete bipartite graph $K\_{n,n}$ for some $n > 1$ as a subgraph has tree-width at most $3k(n − 1) − 1$. It's possible to take $n=3$ for random regular graphs, thus the clique-width is also $\Theta(n)$.


