Пузынина С. А.
О периодичности совершенных раскрасок бесконечной гексагональной и треугольной решеток

Раскраска вершин графа G называется r-совершенной, если цветовой состав всякого шара радиуса r в графе G зависит только от цвета его центра. Параметры совершенной раскраски задаются матрицей A = (a_ij )ⁿ _i,j=1, где n — число цветов, a_ij — число вершин цвета j в шаре с центром в вершине цвета i. Исследуется периодичность совершенных раскрасок графов бесконечной гексагональной и треугольной решеток. Доказано, что для любой 1-совершенной раскраски бесконечной треугольной и любой 1- и 2-совершенной раскраски бесконечной гексагональной решеток существует периодическая совершенная раскраска с той же матрицей параметров. Периодичность совершенных раскрасок для больших r исследована ранее.

Puzynina S. A.
On periodicity of perfect colorings of the infinite hexagonal and triangular grids

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 )ⁿ _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.

Полный текст статьи / Full texts:

• PDF file
• PostScript file