Given any $n \geq 1$ consider the $n \times n$ grid graph.
For example, for $n = 3$, this looks like:
$$\begin{matrix}1&-&2&-&3\\|&&|&&|\\4&-&5&-&6\\|&&|&&|\\7&-&8&-&9\end{matrix}$$
The tree width has a somewhat roundabout definition. The way we did it it: consider any ordering on the vertices- and then remove the vertices one by one; every time you remove a vertex add an edge between the neighbors of the vertex being removed. Then this gives you a bunch of new edges based on the ordering of the vertices. Then combine the new edges with the old edges- the elimination width with respect to this ordering is the maximal clique with this new augmented edge set. The tree width is the least possible edge set.
So yeah, a bit convoluted- but I think there's a bunch of different definitions and whichever is fine.
I would like to find an upper bound on the tree width for the $n \times n$ grid. Obviously I would like a reasonable upper bound, something less than $n^2$ which is the biggest possible clique with these vertices.
I'm pretty sure intuitively that the tree width is actually $n + 1$ exactly - this can be seen by eliminating the vertices by iteratingly removing the corners of the grid. So in the $3 \times 3$ grid you first remove the corners $1, 3, 7, 9$ and then you get a new graph and remove those corners $2, 4, 8, 6$ and so on. This adds minimal edges and so this elimination width will witness the tree width. In the case of $3 \times 3$ one can easily check that the maximal clique is indeed $4 = 3 + 1$.
But I am unable to prove it for general $n$.
I merely need a (reasonable) upper bound however, so I'm fine with just that if proving the exact value is too involved.
Any ideas?
In the case of the gride 3x3 consider the tree descomposición given by the path $P_{6}=t_{1}\cdots t_{6}$, where $t_{i}=\{i,i+1,i+2,i+3\}$ for $i=1,\cdots ,6$. Thus the tree width is ≤3.
Indeed, in any nxn grid we can check that the tw is n.