Welsh & Powell Algorithm

Welsh & Powell algorithm is an algorithm to colour vertex of a graph distinctly based on association of a vertex to another vertex. The idea is to give a vertex different from another vertex that is adjacent to it. This algorithm is used in many different application, such as to make a schedule that each agenda are not clash to another, and even to separate items that should be in different room like hazardous chemical compound should be in different room. It is also used on map to distinctly create boundary that define where is each region on the map.

Colours that is generated from this algorithm is the minimum number of colours to colour the graph. This number is called the chromatic number of the graph.

The Welsh & Powell algorithm works in several simple steps. First of all, we need to sort each vertex based on its degree in descending order. Degree of vertex is how many edges of associate to that vertex.

The second step is to give a colour the first vertex of vertices that we have sorted. Then, we colour next vertex, and so on. But the rule is if the next vertex (lets called vertex P) has adjacent to vertex that already has colour, then vertex P must have different colour. These two steps are repeated until all vertex is coloured.

Let’s consider this example of graph to be coloured using Welsh & Powell algorithm.

First, we generate a table that sort all the vertex based on its degree.

Vertex	Degree
H	11
I	6
A	5
G	5
L	5
C	4
J	4
K	4
E	4
N	4
B	3
F	3
M	3
D	3

Then, we colour each vertex based on order that we have created with colours.

As you can see on the example, this graph has chromatic number of 4 (four).