# Optimal polyomino induced coloring

Which polyominos (with orientation) of $n$ squares, requires the least number of different colors, $c(n)$, such that if this polyomino is placed anywhere on an optimally colored infinite square grid of $c(n)$ colors, it will have all its squares placed on different colors?

And which polyomino(s) require the most colors, and how many colors as a function of $n$?

Also: How to show that a finite number of colors (depending on n), suffices for any subset of n unit-m-cubes, in Z^m?

-
Maybe the more natural question is for which not necessarily connected set of n squares – TROLLKILLER Jan 4 '12 at 12:43
– joriki Jan 4 '12 at 13:20
Brooks' theorem says that the chromatic number of a graph is at most $\Delta + 1$, where $\Delta$ is the maximum vertex degree (and is only $\Delta + 1$ if the graph is complete or an odd cycle). A set of $n$ points in $\mathbb{Z}^m$ has at most $n(n-1)$ different vector separations between distinct points, so the induced graph (which is regular) has degree at most $n(n-1)$, and can't be either complete or an odd cycle; so $n(n-1)$ colors will always suffice. – mjqxxxx Jan 4 '12 at 19:06

Rectangular $n$-ominoes have $c(n)=n$, the minimal possible value.

Let’s call polyominoes for which $c(n)=n$, “optimal”. Colouring the grid with diagonal stripes shows that thin snake-like directed polyominoes such as the following are also optimal.

$\hspace{2.5in}$

Optimal polyominoes can’t be arch-shaped like the following; each of the cells in the ‘gap’ have to differ in colour from all the cells in the arch shape.

$\hspace{2.75in}$

This is a particular case of the following condition on optimal polyominoes.

If $P=\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\}$ is an $n$-omino with the $(x_i,y_i)$ being the cell coordinates, then let $P+v$ be $P$ translated by vector $v$, and let $$D(P)=\{(x_i-x_j,y_i-y_j):(x_i,y_i)\in P,(x_j,y_j)\in P\}$$ be the “distance polyomino” of $P$. For example, the distance polyomino of the ‘F’ pentomino (on it’s ‘back’) looks like this (distance polyominoes are always centrally symmetric):

$\hspace{2.75in}$

Now if for any cell $v\notin P$, we have $P\subset D(P)+v$, then $P$ is not optimal, because there is no way to colour $v$.

As well as excluding arch-shapes, this condition excludes others from being optimal, such as this hexomino:

$\hspace{2.75in}$

This condition can be generalised as follows:

If for any $S\subseteq P$ and any cell $v$ such that $S+v\cap P=\varnothing$, we have $$\left|\;\bigcup_{u\in S}\;P\;\setminus (D(P)+u+v)\;\right|<|S|,$$ then $P$ is not optimal, because there is no way to colour the cells in $S$.

This generalised condition excludes the ‘T’ pentomino from being optimal (the two cells on one side of the stroke cannot be coloured). However, it fails to exclude the ‘F’ pentomino (which is also non-optimal).

Many polyominoes can be seen to be optimal simply by (rotating and) numbering the cells from left-to-right, top-to-bottom in the natural manner. If in the result, the numbers down the columns form arithmetic progressions with the same difference in each column, then the polyomino is optimal (cycle all the colours on every row). This works for rectangles, snake-like directed polyominoes, all row-convex polyominoes with only two rows, and all pentominoes except the ‘U’, ‘T’ and ‘F’ (which are all non-optimal). It also works for some non-convex polyominoes, like this octomino:

$\hspace{3.1in}$

Also, any row-convex polyomino in which each row is the same length is also optimal (cycle the colours on each row). Thus the following (non-convex) hexomino is optimal:

$\hspace{3in}$

Are there any optimal polyominoes that are neither row- nor column-convex?

-
By "As well as excluding non-convex polyominoes", I think you mean "As well as excluding some non-convex polyominoes"? Otherwise your last two examples would be counterexamples. – joriki Jan 5 '12 at 11:18
@joriki: Corrected; thanks. – David Bevan Jan 5 '12 at 12:53