3
$\begingroup$

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?

  • 0
    Maybe the more natural question is for which not necessarily connected set of n squares2012-01-04
  • 0
    See also [Minimum colors needed to color $\mathbb Z^2$ with connected subsets restriction](http://math.stackexchange.com/q/95790/6622).2012-01-04
  • 0
    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.2012-01-04

1 Answers 1