Geodesic
Perfect colorings of radius $r>1$ of the infinite rectangular grid
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 5 (2008), pp. 283-292

Voir la notice de l'article provenant de la source Math-Net.Ru

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, perfect code, graph of the infinite rectangular grid.
Mots-clés : equitable partition 
@article{SEMR_2008_5_a20,
     author = {S. A. Puzynina},
     title = {Perfect colorings of radius $r>1$ of the infinite rectangular grid},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {283--292},
     publisher = {mathdoc},
     volume = {5},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2008_5_a20/}
}
TY  - JOUR
AU  - S. A. Puzynina
TI  - Perfect colorings of radius $r>1$ of the infinite rectangular grid
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2008
SP  - 283
EP  - 292
VL  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2008_5_a20/
LA  - en
ID  - SEMR_2008_5_a20
ER  - 
%0 Journal Article
%A S. A. Puzynina
%T Perfect colorings of radius $r>1$ of the infinite rectangular grid
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2008
%P 283-292
%V 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2008_5_a20/
%G en
%F SEMR_2008_5_a20
S. A. Puzynina. Perfect colorings of radius $r>1$ of the infinite rectangular grid. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 5 (2008), pp. 283-292. http://geodesic.mathdoc.fr/item/SEMR_2008_5_a20/