PERFECT COLORINGS OF RADIUS <i>r > </i>1 OF THE INFINITE RECTANGULAR GRID
A coloring of vertices of a graph G with n colors is called perfect of radius r if the number of vertices of each color in a ball of radius r 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 r > 1 of this graph is periodic.