RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2012, том 19, выпуск 6, страницы 37–48 (Mi da710)

Эта публикация цитируется в 11 статьях

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

Д. С. Малышевab

a Высшая школа экономики в Нижнем Новгороде, Н. Новгород, Россия
b Нижегородский гос. университет им. Н. И. Лобачевского, Н. Новгород, Россия

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

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

УДК: 519.178

Статья поступила: 29.12.2011
Переработанный вариант: 24.03.2012


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2013, 7:2, 221–228

Реферативные базы данных:


© МИАН, 2024