Том 24, номер 3, 2017 г., Стр. 20-34

УДК 519.174.7
Лисицына М. А., Паршина О. Г.
Совершенные раскраски бесконечного циркулянтного графа с дистанциями 1 и 2

Аннотация:
Раскраску вершин графа называют совершенной, если все его одинаково окрашенные вершины имеют одинаковый цветовой состав окружения. Бесконечным циркулянтным графом со сплошным набором n дистанций назовём граф Кэли группы $\mathbb Z$ с системой образующих {$1, 2, \dots , n$}. В статье получено описание всех совершенных раскрасок такого графа с дистанциями 1 и 2 в произвольное конечное число цветов. В 2015 г. была сформулирована гипотеза, характеризующая совершенные раскраски бесконечных циркулянтных графов со сплошным набором $n$ дистанций. Полученный результат подтверждает гипотезу для $n = 2$, в случае $n > 2$ вопрос остаётся открытым.
Библиогр. 12.

Ключевые слова: совершенная раскраска, циркулянтный граф.

DOI: 10.17377/daio.2017.24.559

Лисицына Мария Александровна ¹
Паршина Ольга Геннадьевна ^2,3
1. Военная академия связи им. Маршала Советского Союза С. М. Буденного,
Тихорецкий пр., 3, 194064 Санкт-Петербург, Россия
2. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
3. Institut Camille Jordan, Universit´e Claude Bernard Lyon 1,
43 Boulevard du 11 novembre 1918, F-69622 Villeurbanne Cedex, France
е-mail: lisicinama@ngs.ru, parolja@gmail.com

Статья поступила 2 декабря 2016 г.
Исправленный вариант — 30 марта 2017 г.

Литература

[1] Августинович С. В., Васильева А. Ю., Сергеева И. В. Дистанционно регулярные раскраски бесконечной квадратной решётки // Дискрет. анализ и исслед. операций. 2011. T. 18, № 3. С. 3–10.

[2] Августинович С. В., Лисицына М. А. Совершенные 2-раскраски транзитивных кубических графов // Дискрет. анализ и исслед. операций. 2011. T. 18, № 2. С. 3–17.

[3] Лисицына М. А. Совершенные 3-раскраски графов призмы и лестницы Мёбиуса // Дискрет. анализ и исслед. операций. 2013. T. 20, №1. С. 28–36.

[4] Лисицына М. А., Августинович С. В. Совершенные раскраски призмы // Сиб. электрон. мат. изв. 2016. T. 13. С. 1116–1128.

[5] Паршина О. Г. Совершенные 2-раскраски бесконечных циркулянтных графов со сплошным набором дистанций // Дискрет. анализ и исслед. операций. 2014. T. 21, № 2. С. 76–83.

[6] Пузынина С. А. Совершенные раскраски вершин графа $G(Z^2)$ в три цвета // Дискрет. анализ и исслед. операций, Сер. 2. 2005. T. 12, № 1. С. 37–54.

[7] Хорошилова Д. Б. О циркулярных совершенных раскрасках в два цвета // Дискрет. анализ и исслед. операций. 2009. T. 16, № 1. С. 80–92.

[8] Хорошилова Д. Б. О параметрах совершенных 2-раскрасок циркулянтных графов // Дискрет. анализ и исслед. операций. 2011. T. 18, № 6. С. 82–89.

[9] Цветкович Д., Дуб М., Захс Х. Спектры графов. Киев: Наукова думка, 1984. 384 с.

[10] Axenovich M. A. On multiple coverings of the infinite rectangular grid with balls of constant radius // Discrete Math. 2003. Vol. 268, No. 1–3. P. 31–48.

[11] Parshina O. G. Perfect $k$-colorings of infinite circulant graphs with a continuous set of distances // Abs. Int. Conf. PhD Summer School “Groups and Graphs, Algorithms and Automata” (Yekaterinburg, Aug. 9–15, 2015) Yekaterinburg: UrFU Publ., 2015. P. 80.

[12] Puzynina S. А., Avgustinovich S. V. On periodicity of two-dimensional words // Theor. Comput. Sci. 2008. Vol. 391. P. 178–187.