Исследование граничных классов графов для задач о раскраске

Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной $k$-раскраске и её “предельного варианта” – задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к рёберному варианту задачи о раскраске. Оказывается, что любой класс, граничный для задачи о рёберной $3$-раскраске, является граничным для задачи о хроматическом индексе. Вместе с тем, при любом $k>3$ существует континуум классов графов, граничных для задачи о рёберной $k$-раскраске, каждый из которых не является граничным для задачи о хроматическом числе. Формулируется необходимое условие существования граничных классов графов для задачи о вершинной $3$-раскраске, не являющихся граничными для задачи о хроматическом числе. По мнению автора, заключение этого условия никогда не выполняется, поэтому таковых классов вовсе не существует. Библиогр. 11.