PERFECT COLORINGS OF RADIUS <i>r > </i>1 OF THE INFINITE RECTANGULAR GRID
A coloring of vertices of a graph <i>G </i>with <i>n </i>colors is called <i>perfect of radius r </i>if the number of vertices of each color in a ball of radius <i>r </i>depends only on the color of the center of this ball. Perfect colorings of radius 1 have been studied before under different names including equitable partitions. The notion of perfect coloring is a generalization of the notion of a perfect code, in fact, a perfect code is a special case of a perfect coloring. We consider perfect colorings of the graph of the infinite rectangular grid. Perfect colorings of the infinite rectangular grid can be interpreted as two-dimensional words over a finite alphabet of colors. We prove that every perfect coloring of radius <i>r > </i>1 of this graph is periodic.