Том 18, номер 2, 2011 г., Стр. 3-17
УДК 621.391.15
Августинович С. В., Лисицына М. А.
Совершенные 2-раскраски транзитивных кубических графов
Аннотация:
Для всех транзитивных кубических графов с числом вершин, не превосходящим 18, получено полное описание допустимых параметров совершенных 2-раскрасок.
Ил. 16, библиогр. 13.
Ключевые слова: кубический граф, транзитивный граф, совершенная раскраска.
Августинович Сергей Владимирович 1,2
Лисицына Мария Александровна 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: avgust@math.nsc.ru, lisiсinama@math.nsc.ru
Статья поступила 16 августа 2010 г.
Литература
[1] Августинович С. В., Бородин О. В., Фрид А. Э. Дистрибутивные раскраски плоских триангуляций минимальной степени 5 // Дискрет. анализ и исслед. операций. Сер. 1. — 2001. — Т. 8, № 3. — С. 3–16.
[2] Августинович С. В., Могильных И. Ю. Совершенные раскраски графов Джонсона $J$(8, 3) и $J$(8, 4) в два цвета // Дискрет. анализ и исслед. операций. — 2010. — Т. 17, № 2. — С. 3–19.
[3] Визинг В. Г. Дистрибутивная раскраска вершин графа // Дискрет. анализ и исслед. операций. — 1995. — Т. 2, № 4. — С. 3–12.
[4] Воробьев К. В., Фон-Дер-Флаасс Д. Г. О совершенных 2-раскрасках гиперкуба // Сиб. электрон. мат. изв. — 2010. — Т. 7. — С. 65–75.
[5] Дистель Р. Теория графов. — Новосибирск: Изд-во Ин-та математики, 2002. — 336 с.
[6] Кохов В. А. Диаграммы, числа стабильности и цикловые индексы групп автоморфизмов транзитивных графов // Исследования по прикладной теории графов. — Новосибирск: Наука, 1986. — С. 113–114.
[7] Кротов Д. С. О совершенных раскрасках половинного 24-куба // Дискрет. анализ и исслед. операций. — 2008. — Т. 15, № 5. — С. 35–46.
[8] Фон-Дер-Флаасс Д. Г. Совершенные 2-раскраски гиперкуба // Сиб. мат. журн. — 2007. — Т. 48, № 4. — С. 924—931.
[9] Хорошилова Д. Б. О циркулярных совершенных раскрасках в два цвета // Дискрет. анализ и исслед. операций. — 2009. — Т. 16, № 1. — С. 80–92.
[10] Цветкович Д., Дуб М., Захс Х. Спектры графов. — Киев: Наукова думка, 1984. — С. 121–138.
[11] Avgustinovich S. V., Mogilnykh I. Yu. Perfect 2-colorings of Johnson graphs $J$(6, 3) and $J$(7, 3) // ICMCTA’2008 (Castillo de la Mota, Medina del Campo, Spain, September 15–19, 2008). Proc.: — Berlin: Springer-Verl., 2008. — P. 11—19. (Lect. Notes Comp. Sci.; Vol. 5228.)
[12] Axenovich M. A. On multiple coverings of the infinite rectangular grid with balls of constant radius // Discrete Math. — 2003. — Vol. 268, N 1–3. — P. 31–49.
[13] Puzynina S. A., Avgustinovich S. V. On periodicity of two-dimensional words // Theor. Comput. Sci. — 2008. — Vol. 391. — P. 178–187.
|