In graph theory, vertex colouring is a way of labelling each individual vertex such that no two adjacent vertex have same colour. But we need to find out the number of colours we need to satisfy the given condition. It is not desirable to have a large variety of colours or labels. So, We have an algorithm called welsh Powell algorithm that gives the minimum colours we need. This algorithm is also used to find the chromatic number of a graph. This is an iterative greedy approach.
Chromatic number : A graph G that requires K distinct colors for it’s proper coloring, and no less, is called a K-chromatic graph, and the number K is called the chromatic number of graph G.
Welsh Powell Algorithm consists of following Steps :
- Find the degree of each vertex
- List the vertices in order of descending degrees.
- Colour the first vertex with color 1.
- Move down the list and color all the vertices not connected to the coloured vertex, with the same color.
- Repeat step 4 on all uncolored vertices with a new color, in descending order of degrees until all the vertices are coloured.
By starting with the highest degree, we make sure that the vertex with the highest number of conflicts can be taken care of as early as possible.
| Vertex | Degree |
|---|---|
| A | 2 |
| B | 2 |
| C | 1 |
| D | 4 |
| E | 2 |
| F | 2 |
| G | 3 |
| H | 5 |
| I | 3 |
| J | 3 |
| K | 5 |
First, order the list in descending order of degrees. Incase of tie, we can randomly choose any ways to break it.
So, the new order will be : H, K, D, G, I, J, A, B, E, F, C
Now, Following Welsh Powell Graph colouring Algorithm,
H – color Red
K – don’t color Red, as it connects to H
D – color Red
G – don’t color Red, as it connects to H
I – don’t color Red, as it connects to H
J – don’t color Red, as it connects to H
A – don’t color Red, as it connects to H
B – don’t color Red, as it connects to D
E – colour Red
F – don’t color Red, as it connects to E
C – don’t color Red, as it connects to D
After this, the graph will look like the one below.
Ignoring the vertices already coloured, we are left with : K, G, I, J, A, B, F, C
We can repeat the process with the second colour Green
K – color green
G – don’t color green, as it connects with K
I – color green
J – don’t color green, as it connects with I
A – color green
B – don’t color green, as it connects with A
F – color green
C – color green
Again, ignoring the coloured vertices, we are left with G, J, B Let’s color it with Blue.
G – color blue
J – color blue
B – color blue
The final figure is shown below. Now, we can see that using Welsh Powell’s algorithm we can color the vertices with only 3 types of colors(chromatic number of this graph is 3) which is the optimal solution, since this graph contains at least one triangle.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
