Двухшаговая раскраска графов решетки различных типов

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