Abstrakt
Let Q(n) be the 3-dimensional n x n x n grid with all non-decreasing diagonals (including the facial ones) in its constituent unit cubes. Suppose that a set S subset of V (Q(n)) separates the left side of the grid from the right side.
We show that S induces a subgraph of tree-width at least n/root 18 - 1 We use a generalization of this claim to prove that the vertex set of Q(n) cannot be partitioned to two parts, each of them inducing a subgraph of bounded tree-width.