Том 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 г.

Литература

[1] Визинг В. Г. Об оценке хроматического класса p-графа // Дискрет. анализ. — 1964. — Т. 3. — С. 25–30.

[2] Малышев Д. С. Континуальные множества граничных классов графов для задач о раскраске // Дискрет. анализ и исслед. операций. — 2009. — Т. 16, № 5. — С. 41–51.

[3] Малышев Д. С. О пересечении и симметрической разности семейств граничных классов для задач о раскраске и о хроматическом числе // Дискрет. математика. — 2012. — Т. 24, № 2. — С. 75–78.

[4] Alekseev V. E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Appl. Math. — 2004. — Vol. 132. — P. 17–26.

[5] Alekseev V. E., Boliac R., Korobitsyn D. V., Lozin V. V. NP-hard graph problems and boundary classes of graphs // Theor. Comput. Sci. — 2007. — Vol. 389. — P. 219–236.

[6] Bodlaender H. L. Dynamic programming on graphs with bounded treewidth // Automata, languages, and programming (Tampere, 1988). Proc. — Berlin: Springer-Verl., 1988. — P. 105–118. (Lect. Notes Comput. Sci.; Vol. 317).

[7] Korpeilainen N., Lozin V. V., Malyshev D. S., Tiskin A. Boundary properties of graphs for algorithmic graph problems // Theor. Comput. Sci. — 2011. — Vol. 412. — P. 3545–3554.

[8] Lozin V. V., Rautenbach D. Оn the band-, tree- and clique-width of graphs with bounded vertex degree // Discrete Math. — 2004. — Vol. 18. — P. 195–206.

[9] Machado R., de Figueiredo C. M. H. Complexity separating classes for edge-colouring and total-colouring // J. Braz. Comput. Soc. — 2011. — Vol. 17. — P. 281–285.

[10] Machado R., de Figueiredo C. M. H., Vuskovic K. Chromatic index of graphs with no cycle with a unique chord // Theor. Comput. Sci. — 2010. — Vol. 411. — P. 1221–1234.

[11] Schrijver A. Combinatorial optimization — polyhedra and efficiency. — Berlin: Springer-Verl., 2003. — 1882 p.