A square-grid coloring problem

Abstract

Suppose that $n\ge 2$, and we wish to plant $k$ different types of trees in the squares of an $n\times n$ square grid. We can have as many of each type as we want. The only rule is that every pair of types must occur in an adjacent pair of squares somewhere in the grid. The question is: given $n$, what is the largest that $k$ can be? Denote this number by $\Gamma (n)$, and call this the *complete coloring number* of the $n\times n$ grid. A little thought shows that $\Gamma (n)\le 2n-1$. The main question we are interested in is whether $\Gamma (n)=2n-1$ for every $n\ge 2$.

18 pages; 9 figures, 1 table