EN|RU

Том 19, номер 6, 2012 г., Стр. 37-48

УДК 519.178
Малышев Д. С. 
Исследование граничных классов графов для задач о раскраске

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

Ключевые слова: вычислительная сложность, граничный класс графов, задача о раскраске.

Малышев Дмитрий Сергеевич 1,2
1. Высшая школа экономики в Нижнем Новгороде,
ул. Б. Печёрская, 25/12, 603155 Н. Новгород, Россия
2. Нижегородский гос. университет им. Н. И. Лобачевского,
пр. Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия
е-mail: dsmalyshev@rambler.ru

Статья поступила 29 декабря 2011 г.
Исправленный вариант — 24 марта 2012 г.

 © Институт математики им. С. Л. Соболева, 2015