Welsh-Powell Algorithm


(Team) #1

Reading time: 20 minutes | Coding time: 9 minutes

In graph theory, Welsh Powell is used to implement graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.
In 1967 Welsh and Powell introduced in an upper bound to the chromatic number of a graph . It provides a greedy algorithm that runs on a static graph.
The vertices are ordered according to their degrees, the resulting greedy coloring uses at most $max_i min{ d(x_i) + 1, i}$ colors, at most one more than the graph’s maximum degree. This heuristic is called the Welsh–Powell algorithm.

This is a companion discussion topic for the original entry at http://iq.opengenus.org/welsh-powell-algorithm/