# Minimum colors needed to color $\mathbb Z^2$ with connected subsets restriction

What is the minimum number of colors needed to color every unit square of $\mathbb Z^2$ such that if any polyomino of order $n$ is placed anywhere on the grid it would have all its unit-squares placed on squares of different colors?

-
@matt: I restored "polyomino", which I believe was the intended meaning. I never heard of a "polyominal", and in case you meant "polynomial", I don't think that's what's intended. – joriki Jan 2 '12 at 13:05
@Chandrasekhar: No problem; I'd already deleted my comment because I realized you'd been editing an old version and probably hadn't seen this one yet. – joriki Jan 2 '12 at 13:33
@joriki (also 0.99999....9999) Yes, my apologies. I wasn't careful enough in reading the post. – matt Jan 2 '12 at 13:37
Is the question about the chromatic number of the graph induced by a particular polyomino, or the set of all polyominoes of order $n$? The latter is just the distance graph for $d\le n-1$. The former might be more interesting... – mjqxxxx Jan 2 '12 at 13:46

For odd $n$, the answer is $(n^2+1)/2$.

To see that this number is necessary, consider a diamond-shaped patch of $(n^2+1)/2$ squares. They are all within a distance of $n-1$ of each other, and thus must all have different colours.

To see that this number is sufficient, consider the colouring $x+ny\,\bmod\,{(n^2+1)/2}$. Equicoloured squares within a row are $(n^2+1)/2\ge n$ apart. Equicoloured squares in consecutive rows are $n+1$ apart, and this increases until the progression wraps around and gets close to $0$ again. This happens at $\Delta y=(n\pm1)/2$, and the corresponding distances are

$$\frac{n\pm1}2+\left|\frac{n^2+1}2-\frac{n(n\pm1)}2\right|=\frac{n\pm1}2+\frac{n\mp1}2=n\;.$$

The next wraparound occurs at $\Delta y=n$, and then the distance in the $y$ direction is already enough.

For even $n$, the answer is $n^2/2$.

To see that this number is necessary, consider a diamond-shaped patch of $n^2/2-n+1$ squares and shift it to the right by one to add another $n-1$ squares, for a total of $n^2/2$. The squares in this shape are all within a distance of $n-1$ of each other, and thus must all have different colours.

To see that this number is sufficient, consider the colouring $x+(n-1)y\,\bmod\,n^2/2$. Equicoloured squares within a row are $n^2/2\ge n$ apart. Equicoloured squares in consecutive rows are $n$ apart, and this increases until the progression wraps around and gets close to $0$ again. This happens at $\Delta y=n/2$, where the distance is $n/2+n^2/2-(n-1)n/2=n$, and at $\Delta y=n/2+1$, where the distance is also $n/2+1+(n-1)(n/2+1)-n^2/2=n$. The next wraparound occurs at $\Delta y=n+1$, and then the distance in the $y$ direction is already enough.

-