用于图形着色的Himpling算法

Question

任何人都知道Himpling的贪婪图着色算法的最坏情况(即其着色和最佳着色之间的最坏比率是多少(。

基本算法为每个顶点着色一种颜色，然后在顶点颜色与公共边上的现有顶点碰撞时重复递增顶点颜色。这与维基百科上的标准贪婪着色相似，但并不完全相同。

Answer 1

由Brook定理给出了色数(最优着色(与图最大度之间的一个关系。

假设Himpling算法的意思是：

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。