EUVIMEDEUVIMED entdecken
Crossref

Некоторые классификации сложности задачи о вершинной 3-раскраске

Grigoriy Sergeevich Dakhno, Dmitriy Sergeevich Malyshev

Математические заметки · 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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →