Раскраска вершин графа при мажоритарных ограничениях на используемые цвета

Рассматривается задача раскраски вершин графа при условии, что для каждой вершины указывается мажорирующий, т.е. максимальный допустимый цвет. Приводится критерий “хроматичности” такого предписания, обобщающий теорему Витавера. Оценивается наибольшее значение мажорирующего цвета, которое может потребоваться для хроматичности предписания. Приводятся аналоги теоремы Нордхауза и Гаддума, касающиеся зависимости между хроматическими характеристиками графа и его дополнения. Библиогр. 7.