Abstract:
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})^n_{i,j=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.
Fulltext:
PDF file (461 kB)
