Пузынина С. А.
О периодичности совершенных раскрасок бесконечной гексагональной и треугольной решетокРаскраска вершин графа G называется r-совершенной, если цветовой состав всякого шара радиуса r в графе G зависит только от цвета его центра. Параметры совершенной раскраски задаются матрицей A = (aij )n i,j=1, где n — число цветов, aij — число вершин цвета j в шаре с центром в вершине цвета i. Исследуется периодичность совершенных раскрасок графов бесконечной гексагональной и треугольной решеток. Доказано, что для любой 1-совершенной раскраски бесконечной треугольной и любой 1- и 2-совершенной раскраски бесконечной гексагональной решеток существует периодическая совершенная раскраска с той же матрицей параметров. Периодичность совершенных раскрасок для больших r исследована ранее.
Puzynina S. A.
On periodicity of perfect colorings of the infinite hexagonal and triangular gridsA 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 = (aij )n i,j=1 , where n is the number of colors and aij 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.
Полный текст статьи / Full texts: