Why is Welsh-Powell algorithm better than the basic greedy algorithm for graph coloring?

4.4k Views Asked by At

I am not able to find any reason that why Welsh-Powell algorithm works better than the basic greedy algorithm for graph coloring.

In Welsh-Powell algorithm, the only thing that differs from the basic greedy algorithm for graph coloring, is that it visits the vertices in decreasing order of degree. How does this help it in getting bette results?

You can read about the basic greedy algorithm for graph coloring here.

1

There are 1 best solutions below

2
On

Note that Welsh-Powell is a special case of the basic greedy algorithm, all it does is to suggest a more specific order instead of an arbitrary order in which the vertices are visited. The idea is based on heuristics as follows: A new colour needs to be created in (any variant of) the greedy algorithm whenever the current vertex has all colours created so far among its already visitedneighbours. This unwanted situation can only occur for vertices of sufficiently high degree that are visited after sufficiently many of their neighbours. Hence if we try to visit all high-degree vertices before their neighbours, the "risk" of requiring a new colour should decrease.

Whether this is better on average is a tough question. However, the worst case of Greedy is $\max_v \deg(v)+1$ whereas for Welsh-Powell it is $\max_i \min\{\deg(v_i)+1,i\}$, which is strictly less in most cases.