УДК 519.17
Полная классификация сложности задачи о вершинной 3-раскраске для четверок порожденных 5-вершинных запретов
Д. С. Малышев1
| Аннотация | Задача о вершинной 3-раскраске для заданного графа состоит в том, чтобы проверить, возможно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Наследственный класс графов - множество обыкновенных графов, замкнутое относительно изоморфизма и удаления вершин. Любой такой класс может быть задан множеством своих запрещенных порожденных подграфов. Известен сложностной статус задачи о вершинной 3-раскраске для всех четверок 5-вершинных запрещенных порожденных подграфов, кроме трех из них. Более того, известно, что два из этих трех случаев полиномиально эквивалентны и полиномиально сводятся к третьему. В настоящей работе доказывается, что вычислительная сложность рассматриваемой задачи во всех трех упомянутых классах является полиномиальной. Данный результат вносит вклад в алгоритмическую теорию графов. |
|---|---|
| Ключевые слова | задача о вершинной 3-раскраске, наследственный класс, полиномиальный алгоритм |
1Малышев Дмитрий Сергеевич, профессор, кафедра прикладной математики и информатики, ФГАОУ ВО Национальный исследовательский университет "Высшая школа экономики" (603155, Россия, г. Нижний Новгород, ул. Большая Печерская, д. 25/12), профессор, кафедра алгебры, геометрии и дискретной математики, ФГАОУ ВО Национальный исследовательский Нижегородский государственный университет им. Н. И. Лобачевского (603950, Россия, г. Нижний Новгород, пр. Гагарина, д. 23); доктор физико-математических наук, ORCID: http://orcid.org/0000-0001-7529-8233, dsmalyshev@rambler.ru
Цитирование: Малышев Д. С. Полная классификация сложности задачи о вершинной 3-раскраске для четверок порожденных 5-вершинных запретов // Журнал Средневолжского математического общества. 2020. Т. 22, № 1. С. 38–47.
DOI 10.15507/2079-6900.22.202001.38-47
