Том 12, серия 2, номер 1, 2005 г., Стр. 37-54

УДК 621.391.15
С. А. Пузынина
Совершенные раскраски вершин графа $G(Z^2)$ в три цвета

Аннотация:
Раскраска вершин графа называется совершенной, если цветовой состав окружения каждой его вершины однозначно определяется цветом этой вершины. Параметры совершенной раскраски в $n$ цветов задаются квадратной матрицей порядка $n$. Матрица называется допустимой, если существует совершенная раскраска графа $G(Z^2)$ с такой матрицей. Перечислены все допустимые матрицы совершенных раскрасок в три цвета (число таких матриц равно 21), приведены соответствующие примеры раскрасок.

Пузынина С. А. ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия

Статья поступила 27 мая 2004 г.
Исправленный вариант — 15 апреля 2005 г.