Performance ratio of the generalized greedy algorithm for $q$-coloring problem

В данной работе описан обобщенный жадный алгоритм для нахождения $q$-хроматического подграфа, где $q$–натуральное число. Доказано, что отклонение этого алгоритма от оптимального не превосходит $\dfrac{e}{e-1}$ для произвольного $q$. Показано также, что отклонение обычного жадного алгоритма от оптимального тоже не превосходит $\dfrac{e}{e-1}$. Таким образом, прежде найденная оценка $2$ для отклонения обычного жадного алгоритма не достижима.