Некоторые классификации сложности задачи о вершинной 3-раскраске
Математические заметки · 2026 · 119 (3) · 360-376
DOI: 10.4213/mzm14793 ↗Kurz gefasst
Fachartikel in der Zeitschrift Математические заметки, online erschienen am 02.03.2026. Verfasst von Grigoriy Sergeevich Dakhno und 1 weiteren Autor:innen. Die Arbeit nennt 21 Literaturangaben. Gefördert von: HSE Basic Research Program, Ministry of Science and Higher Education of the Russian Federation.
Abstract (Originalsprache)
Наследственный класс - множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-$\mathrm{BP}$) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных классов, определяемых 5-вершинными порожденными запретами. В данной работе для задачи 3-$\mathrm{BP}$ рассматривается вопрос о полной классификации алгоритмической сложности для пар порожденных запретов с 6 вершинами. Известно, что задача 3-$\mathrm{BP}$ будет NP-полной для такого класса, если ни один элемент пары не будет лесом, и что она будет полиномиальной разрешимой, если один из запретов является линейным лесом. В этой работе рассмотрены четыре нелинейных 6-вершинных леса и получены классификации сложности задачи 3-$\mathrm{BP}$ для всех соответствующих пар. Библиография: 21 название.
Förderung
- HSE Basic Research Program
- Ministry of Science and Higher Education of the Russian Federation
Zitieren
APA
Dakhno, G. S., & Malyshev, D. S. (2026). Некоторые классификации сложности задачи о вершинной 3-раскраске. Математические заметки, 119(3), 360-376. https://doi.org/10.4213/mzm14793
Vancouver
Dakhno GS, Malyshev DS. Некоторые классификации сложности задачи о вершинной 3-раскраске. Математические заметки. 2026;119(3):360-376. doi:10.4213/mzm14793
BibTeX
@article{Dakhno2026,
author = {Dakhno, Grigoriy Sergeevich and Malyshev, Dmitriy Sergeevich},
title = {Некоторые классификации сложности задачи о вершинной 3-раскраске},
journal = {Математические заметки},
year = {2026},
volume = {119},
number = {3},
pages = {360--376},
doi = {10.4213/mzm14793}
}
EUVIMED