Цвет графика, чтобы каждый узел был либо цветным, либо рядом с цветным узлом

Question

Предположим, что у вас есть связанный неориентированный граф G. Вы хотите, чтобы каждый узел в G был либо окрашен, либо смежён с цветным узлом. Создайте алгоритм для правильного окрашивания графа G. Вам разрешено указывать только пол (n/2) узлов, где n - общее количество узлов.

Я сделал попытку решения, но я решил, что он не полностью решает проблемы с ограничениями, и мне бы хотелось либо подтолкнуть, либо сказать, что я ошибаюсь.

Моим решением было в основном запустить BFS и покрасить узлы на каждом третьем «уровне». Но я идентифицировал один экземпляр, где это не удалось - только связанный список из трех узлов. Если я покрашу голову или хвост, то один из узлов будет на расстоянии 2 от цветного узла, и я не совсем уверен, как гарантировать, что средний узел будет окрашен.

Answer 1

Выберите корень и сгенерируйте остовное дерево, скажем, DFS.

Затем цветьте узлы на каждом втором уровне. Выберите цвет либо четные уровни, либо нечетные номера, в соответствии с которым выбор будет окрасить наименьшие узлы.