Алгоритм Гимплинга для раскраски графов

Question

Всем известен наихудший случай алгоритма раскраски жадного графа Химплинга (т.е. каково наихудшее соотношение между его раскраской и оптимальной раскраской).

Базовый алгоритм c окрашивает каждую вершину в один цвет, и затем многократно увеличивает цвет вершины, если она сталкивается с существующей вершиной на общем ребре. Это похоже, но не совсем то же самое, что стандартная жадная раскраска в Википедии.

Answer 1

Одно соотношение между числом c цветности (оптимальная окраска) и максимальной степенью графа задается теоремой Брука .

Учитывая, что под алгоритмом Химплинга вы имеете в виду нечто подобное :

while no more (u, v) s.t. u.color == v.color
    for u in V
        for v in V
            if (u, v) in E and u.color == v.color
                v.color = u.color + 1

Наибольшее соотношение должно быть 1/V.