Том 16, номер 1, 2009 г., Стр. 80-92
УДК 519.87
Д. Б. Хорошилова
О циркулярных совершенных раскрасках в два цвета
Аннотация:
Исследуются совершенные раскраски семейства бесконечных графов, называемых циркулярными. Показано, что каждая такая раскраска порождает совершенную раскраску n-мерной бесконечной решётки с теми же параметрами, что и у исходной раскраски. Предложена конструкция для построения совершенных раскрасок циркулярных графов в два цвета, и перечислены все параметры совершенных раскрасок, которые могут быть получены с помощью этой конструкции.
Библиогр. 12.
Ключевые слова: совершенная раскраска, циркулярный граф, равномерное разбиение.
Хорошилова Дарья Борисовна 1
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: dkhor@ngs.ru
Статья поступила 16 сентября 2008 г.
Исправленный вариант — 17 ноября 2008 г.
