УДК 519.17
О сложности построения 3-раскраски планарных графов с короткими гранями
Д. В. Сироткин1
| Аннотация | Задача о вершинной 3-раскраске для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известно, что эта задача является NP-полной в классе планарных графов и что она становится полиномиально разрешимой для плоских триангуляций --- планарных графов, у которых все грани (включая и внешнюю) являются треугольниками. Известно также, что она является NP-полной в классе планарных графов со степенями всех вершин не более чем 4, но становится разрешимой за линейное время в классе графов с максимильной степенью вершин не более чем 3. Поэтому интересен вопрос о поиске порога на значения длин граней и максимальной степени вершин планарных графов, при переходе через который для задачи о вершинной 3-раскраске полиномиальная разрешимость меняется на NP-полноту. В данной работе дается ответ на этот вопрос и доказывается NP-полнота задачи о вершинной 3-раскраске в классе планарных графов, гранями которых являются только треугольники и четырехугольники, с максимальной степенью вершин не более чем 5. |
|---|---|
| Ключевые слова | вычислительная сложность, задача о вершинной 3-раскраске, планарный граф |
1Сироткин Дмитрий Валерьевич, лаборант, кафедры алгебры, геометрии и дискретной математики ФГАОУ ВО "ННГУ им. Н. И. Лобачевского" (603950, Россия, г. Нижний Новгород, пр. Гагарина, д. 23), без ученой степени, ORCID: http://orcid.org/ 0000-0002-2682-9867, dmitriy.v.sirotkin@gmail.com
Цитирование: Сироткин Д. В. О сложности построения 3-раскраски планарных графов с короткими гранями // Журнал Средневолжского математического общества. 2018. Т. 20, № 2. С. 199–205.
DOI 10.15507/2079-6900.20.201802.199-205
