On periodicity of perfect colorings of the infinite hexagonal and triangular grids
Svetlana Puzynina · Siberian Mathematical Journal · 2011
A coloring of vertices of a graph G is called r-perfect, if the color structure of each ball of radius r in G depends only on the color of the center of the ball. The parameters of a perfect coloring are given by the matrix A = (a ij ) =1 , where n is the number of colors and a ij is the number of vertices of color j in a ball centered at a vertex of color i. We study the periodicity of perfect colorings of the graphs of the infinite hexagonal and triangular grids. We prove that for every 1-perfect coloring of the infinite triangular and every 1- and 2-perfect coloring of the infinite hexagonal grid there exists a periodic perfect coloring with the same matrix. The periodicity of perfect colorings of big radii have been studied earlier.