How many pair-wise touching "shapes" are there in an $n\times n\times n$ grid?

Question

Partition an $n\times n\times n$ grid of cubes into "shapes" which are sets of cubes connected by faces. What's the largest number of shapes that can touch every other shape (touching = sharing a face)?

---

Here is an image of the $2$-dimensional version of the problem, which is simple to solve: for $n=1,2,3$ the answers are $1,3$ and $4$ respectively. Presumably for $n\ge4$, the answer is still $4$ or we would have a graph that is not $4$-colourable.

Answer 1

Let $f(n)$ be the maximal number of pair-wise touching "shapes" in an $n\times n\times n$ grid.

---

We have $f(n)\ge n$, as can be seen in the following image from the German Wikipedia article on the "Four color theorem":

For $n\ge 4$ we can stack two such constructs with completely different colors to find $f(n)\ge 2n$. This might be best possible, but I do not know. The remaining cases are as follows:

• $f(1)=1$, obviously.
• $f(2)=4$, and this is best possible.

Proof.

If more than four shapes are used, then one of the shapes must consists of a single cube. This cube must be places in one of the corners of the grid. But then there are only three remaining faces with which it can touch other shapes. So no fifth shape can touch this cube.

• $f(3)\ge 5$, and I am not sure whether $6$ is possible. But I do not think so.

---

By the way, I think your question can be asked in purely graph theoretical terms:

The $n\times n\times n$ grid graph $G$ is given by $V(G)=\{1,...,n\}^3$ and $$E(G)=\left\{\{v,w\}\in {V\choose 2}\;\middle|\; |v-w|_1=1\right\}.$$ What is the biggest $k$ so that the complete graph $K_k$ is a minor of $G$?