Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/343991| Заглавие документа: | О случаях полиномиальной разрешимости задачи о рёберной раскраске, порождаемых запрещёнными 8-рёберными субкубическими лесами |
| Другое заглавие: | Some cases of polynomial solvability for the edge colorability problem generated by forbidden 8-edge subcubic forests |
| Авторы: | Малышев, Д.С. Дугинов, О.И. |
| Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Кибернетика ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
| Дата публикации: | 2022 |
| Издатель: | Институт математики им. С. Л. Соболева СО РАН |
| Библиографическое описание источника: | Дискретный анализ и исследование операций.2022; Т. 29(2)(152):С. 38-61 |
| Аннотация: | Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы смежные рёбра были окрашены в разные цвета. Для всех классов графов, определяемых множествами запрещённых подграфов с 7 рёбрами каждый, известен сложностной статус данной задачи. В настоящей работе рассматривается случай запретов с 8 рёбрами. Нетрудно заметить, что задача о рёберной раскраске будет NP-трудной для такого класса, если среди его 8-рёберных запретов нет субкубического леса. В данной работе доказывается, что запрещение любого субкубического 8-рёберного леса порождает класс с полиномиальной разрешимостью задачи о рёберной раскраске, кроме случаев, образованных дизъюнктной суммой одного из четырёх лесов и пустого графа. Для всех оставшихся случаев доказывается аналогичный результат для пересечения с множеством графов максимальной степени не менее чем 4. Ил. 2, библиогр. 14. |
| Аннотация (на другом языке): | The edge-coloring problem, is to minimize the number of colors sufficient to color all the edges of a given graph so that any adjacent edges receive distinct colors. For all the classes defined by sets of forbidden subgraphs with 7 edges each, the complexity status of this problem is known. In this paper, we consider the case of prohibitions with 8 edges. It is not hard to see that the edge-coloring problem is NP-complete for such a class if there are no subcubic forests among its 8-edge prohibitions. We prove that forbidding any subcubic 8-edge forest generates a class with polynomial-time solvability of the edgecoloring problem, except for the cases formed by the disjunctive sum of one of 4 forests and an empty graph. For all the remaining four cases, we prove a similar result for the intersection with the set of graphs of maximum degree at least four. Illustr. 2, bibliogr. 14. |
| URI документа: | https://elib.bsu.by/handle/123456789/343991 |
| DOI документа: | 10.33048/daio.2022.29.721 |
| Финансовая поддержка: | Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований и Белорусского республиканского фонда фундаментальных исследований (проект № 20-51-04001 (Ф21РМ-001)). |
| Лицензия: | info:eu-repo/semantics/openAccess |
| Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| da1297.pdf | 383,09 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.