NP-полнота и один полиномиальный подкласс задачи о двухшаговой раскраске графа

Аннотация

В данной статье рассматривается задача о двухшаговой раскраске произвольного неориентированного связного графа. Она состоит в нахождении такой раскраски в заданное число цветов, при которой ни одна пара вершин на расстоянии 1 или 2 друг от друга не будет окрашена в одинаковый цвет. Также в работе ставится соответствующая задача распознавания. Данная задача тесно связана с классической задачей о раскраске графа. В статье рассматривается и обосновывается полиномиальное сведение задач друг к другу. В частности, это позволяет доказать NP-полноту задачи о двухшаговой раскраске. Кроме того, определяются некоторые ее свойства. Отдельно исследуется задача о двухшаговой раскраске в приложении к прямоугольным графам решетки. Максимальная степень вершины таких графов может принимать значение от 0 до 4, и для каждого возможного случая была определена и обоснована функция двухшаговой раскраски в минимальное число цветов. Полученные функции строятся таким образом, что каждая вершина графа может быть раскрашена независимо от остальных, а время раскраски прямоугольного графа решетки полиномиально при последовательном переборе вершин.