Anyone know the worst-case for Himpling's greedy graph coloring algorithm (i.e. what is the worst ratio between its coloring and the optimal coloring).
The basic algorithm colors each vertex one color, and then repeatedly increments a vertex color if it collides with an existing vertex on a common edge. This is similar but not quite the same as the standard greedy coloring on Wikipedia.
One relation between chromatic number (the optimal coloring) and the graph maximum degree is given by Brook's theorem.
Given that by Himpling's algorithm you mean something along these lines:
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
The biggest ratio should be 1/V.
