Map Colouring Algorithm

Map colouring problem states that given a graph G {V, E} where V and E are the set of vertices and edges of the graph, all vertices in V need to be coloured in such a way that no two adjacent vertices must have the same colour.

The real-world applications of this algorithm are assigning mobile radio frequencies, making schedules, designing Sudoku, allocating registers etc.

Map Colouring Algorithm

With the map colouring algorithm, a graph G and the colours to be added to the graph are taken as an input and a coloured graph with no two adjacent vertices having the same colour is achieved.

Algorithm

• Initiate all the vertices in the graph.
• Select the node with the highest degree to colour it with any colour.
• Choose the colour to be used on the graph with the help of the selection colour function so that no adjacent vertex is having the same colour.
• Check if the colour can be added and if it does, add it to the solution set.
• Repeat the process from step 2 until the output set is ready.

Examples

Step 1

Find degrees of all the vertices −

A  4
B  2
C  2
D  3
E  3

Step 2

Choose the vertex with the highest degree to colour first, i.e., A and choose a colour using selection colour function. Check if the colour can be added to the vertex and if yes, add it to the solution set.

Step 3

Select any vertex with the next highest degree from the remaining vertices and colour it using selection colour function.

D and E both have the next highest degree 3, so choose any one between them, say D.

D is adjacent to A, therefore it cannot be coloured in the same colour as A. Hence, choose a different colour using selection colour function.

Step 4

The next highest degree vertex is E, hence choose E.

E is adjacent to both A and D, therefore it cannot be coloured in the same colours as A and D. Choose a different colour using selection colour function.

Step 5

The next highest degree vertices are B and C. Thus, choose any one randomly.

B is adjacent to both A and E, thus not allowing to be coloured in the colours of A and E but it is not adjacent to D, so it can be coloured with Ds colour.

Step 6

The next and the last vertex remaining is C, which is adjacent to both A and D, not allowing it to be coloured using the colours of A and D. But it is not adjacent to E, so it can be coloured in Es colour.

Example

Following is the complete implementation of Map Colouring Algorithm in various programming languages where a graph is coloured in such a way that no two adjacent vertices have same colour.

CC++JavaPython

#include<stdio.h>#include<stdbool.h>#define V 4
bool graph[V][V]={{0,1,1,0},{1,0,1,1},{1,1,0,1},{0,1,1,0},};
bool isValid(int v,int color[],int c){//check whether putting a color valid for vfor(int i =0; i < V; i++)if(graph[v][i]&& c == color[i])return false;return true;}
bool mColoring(int colors,int color[],int vertex){if(vertex == V)//when all vertices are consideredreturn true;for(int col =1; col <= colors; col++){if(isValid(vertex,color, col)){//check whether color col is valid or not
         color[vertex]= col;if(mColoring(colors, color, vertex+1)== true)//go for additional verticesreturn true;
         color[vertex]=0;}}return false;//when no colors can be assigned}intmain(){int colors =3;// Number of colorsint color[V];//make color matrix for each vertexfor(int i =0; i < V; i++)
      color[i]=0;//initially set to 0if(mColoring(colors, color,0)== false){//for vertex 0 check graph coloringprintf("Solution does not exist.");}printf("Assigned Colors are: \n");for(int i =0; i < V; i++)printf("%d ", color[i]);return0;}

Output

Assigned Colors are:
1 2 3 1