Исследование трудоемкости задач о доминирующем множестве и о вершинной 3-раскраске в некоторых наследственных классах графовA study of the complexity for the dominating set and vertex 3-colorability problems in some hereditary graph classes

Диссертация посвящена, в основном, изучению алгоритмической сложности некоторых алгоритмических на графах в наследственных классах графов, определяемых запретами небольшого размера. Основные результаты диссертационного исследования состоят в следующем:
1). Предъявлено счетное семейство граничных классов графов для задачи о доминирующем множестве.
2).  Получены полные классификации сложности задачи о доминирующем множестве для систем запрещенных порожденных подграфов, каждый не более чем с 6 вершинами, включающих 5-путь или 3-вилку.
3).  Получены полные классификации сложности задачи о вершинной 3-раскраске для пар 6-вершинных запрещенных порожденных фрагментов, один из которых --- лес одного из четырех видов.
Результаты диссертации в определенном смысле определяют границу современных знаний в соответствующей проблематике.