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/

[1] M. Axenovich, “On multiple coverings of the infinite rectangular grid with balls of constant radius”, Discrete Mathematics, 268 (2003), 31–49 | DOI | MR

[2] S. I. R. Costa, M. Muniz, E. Agustini, R. Palazzo, “Graphs, tessellations, and perfect codes on flat tori”, Information Theory, IEEE Transactions, 50:10 (Oct. 2004), 2363–2377 | DOI | MR

[3] D. M. Cvetkovic, M. Doob, H. Sachs, Spectra of graphs, VEB Deutcher Verlag der Wissenschaften, Berlin, 1980 | MR | Zbl

[4] D. G. Fon-der-Flaass, “Perfect 2-colorings of a hypercube”, Siberian Mathematical Journal, 48:4 (2007), 740–745 | DOI | MR | Zbl

[5] C. D. Godsil, W. J. Martin, “Quotients of association schemes”, J. Combin. Theory, ser. A, 69:2 (1995), 185–199 | DOI | MR | Zbl

[6] S. W. Golomb, L. R. Welch, “Perfect codes in the Lee metric and the packing of polyominoes”, SIAM J. Appl. Math., 18 (1970), 302–317 | DOI | MR | Zbl

[7] S. W. Golomb and L. R. Welch, “Algebraic coding and the Lee metric”, Error Correcting Codes, Proc. Sympos. Math. Res. Center, Madison, Wis., John Wiley, New York, 1968, 175–194 | MR

[8] S. A. Puzynina, “Periodicity of perfect colorings of the infinite rectangular grid”, Discrete Analysis and Operations Research, 11:1 (2004), 79–92 (in Russian) | MR | Zbl

[9] S. A. Puzynina, “Perfect colorings of the infinite rectangular grid”, Bayreuther Mathematischen Schriften, 74 (2005), 317–331 | MR | Zbl

[10] S. A. Puzynina, S. V. Avgustinovich, “On periodicity of two-dimensional words”, Theoretical Computer Science, 391 (2008), 178–187 | DOI | MR | Zbl