This article is cited in 2 papers

Research papers

Perfect colorings of radius $r>1$ of the infinite rectangular grid

S. A. Puzynina<sup>ab

a</sup> Sobolev Institute of Mathematics, Novosibirsk, Russia
^b Novosibirsk State University

Abstract: 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.

Keywords: perfect coloring, equitable partition, perfect code, graph of the infinite rectangular grid.

UDC: 519.1

MSC: 05E99

Received September 27, 2007, published June 25, 2008

Language: English

Bibliographic databases:

•