Том 16, номер 4, 2009 г., Стр. 21-30
УДК 519.718
В. Г. Визинг
Раскраска вершин графа при мажоритарных ограничениях на используемые цвета
Аннотация:
Рассматривается задача раскраски вершин графа при условии, что для каждой вершины указывается мажорирующий, т. е. максимальный допустимый цвет. Приводится критерий «хроматичности» такого предписания, обобщающий теорему Витавера. Оценивается наибольшее значение мажорирующего цвета, которое может потребоваться для хроматичности предписания. Приводятся аналоги теоремы Нордхауза и Гаддума, касающиеся зависимости между хроматическими характеристиками графа и его дополнения.
Библиогр. 7.
Ключевые слова: мажоритарное предписание, допустимая раскраска, хромат графа.
Визинг Вадим Георгиевич 1
1. Одесская национальная академия пищевых технологий,
ул. Канатная, 112, 65039 Одесса, Украина
е-mail: vizing@paco.net
Статья поступила 20 ноября 2008 г.
Исправленный вариант — 18 мая 2009 г.
