Том 21, номер 2, 2014 г., Стр. 76–83

УДК 519.87
Паршина О. Г.
Совершенные 2-раскраски бесконечных циркулянтных графов со сплошным набором дистанций

Аннотация:
Исследуются совершенные раскраски бесконечных циркулянтных графов с набором дистанций, образующих отрезок натуральных чисел [1, n]. Для этих графов получено полное описание совершенных раскрасок в два цвета и перечислены все их допустимые параметры.
Библиогр. 5.

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

Паршина Ольга Геннадьевна ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: parolja@gmail.com

Статья поступила 22 мая 2013 г.
Исправленный вариант — 8 июля 2013 г.

Литература

[1] Августинович С. В., Лисицына М. А. Совершенные 2-раскраски транзитивных кубических графов // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, № 2. - С. 3–17.
Avgustinovich S. V., Lisitsyna M. A. Perfect 2-colorings of transitive cubic graphs // J. Appl. Industr. Math. - 2011. - Vol. 5, N 4. - P. 519–528.

[2] Лисицына М. А. Совершенные 3-раскраски графов призмы и лестницы Мёбиуса // Дискрет. анализ и исслед. операций. - 2013. - Т. 20, № 1. - С. 28-36.
Lisitsyna M. A. Perfect 3-colorings of prism and MЁobius ladder graphs // J. Appl. Industr. Math. - 2013. - Vol. 7, N 2. - P. 215–220.

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

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

[5] 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–48.