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?
Minimum colors needed to color $\mathbb Z^2$ with connected subsets restriction
-
0Is 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... – 2012-01-02
1 Answers
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.