Том 20, номер 1, 2013 г., Стр. 28-36

УДК 621.391.15
Лисицына М. А.
Совершенные 3-раскраски графов призмы и лестницы Мёбиуса

Аннотация:
Исследуются две бесконечные серии транзитивных кубических графов: призма и лестница Мёбиуса. Для рассматриваемых графов получено полное описание допустимых параметров совершенных раскрасок в 3 цвета.
Ил. 4, библиогр. 7.

Ключевые слова: призма, лестница Мёбиуса, совершенная раскраска.

Лисицына Мария Александровна ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: lisiсinama@math.nsc.ru

Статья поступила 16 ноября 2011 г.
Исправленный вариант — 7 марта 2012 г.

Литература

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

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

[3] Кохов В. А. Диаграммы, числа стабильности и цикловые индексы групп автоморфизмов транзитивных графов // Исследования по прикладной теории графов. - Новосибирск: Наука, 1986. - С. 113–114.

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

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

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

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