Graph Coloring (Backtracking Method)

Graph coloring is a technique to assign colors to the nodes in such a way that either none of the adjacent nodes share same color or none of the adjacent edges share same color.

In a graph if the adjacent vertices do not share same color, the problem is known as vertex coloring. Similarly, if adjacent edges of a graph do not share same color, the problem is known as edge coloring.

This concept is mainly used in the following applications:

• Job scheduling, 
• Register allocation, 
• Pattern matching, 
• Timetable preparation, 
• Seating arrangement etc.

 

In the Graph Coloring Problem, the goal is to assign colors to the vertices of a graph such that no two adjacent vertices share the same color, while using the minimum number of colors possible. This problem can be formally defined as follows:

 

Given a graph G=(V,E)G=(V,E), where VV is a set of vertices and EE is a set of edges, the task is to assign a color to each vertex such that:

• No two adjacent vertices (connected by an edge) share the same color. 
•  Minimize the number of colors used for the entire graph.

The minimum number of colors needed to color a graph is called the chromatic number of the graph, denoted as χ(G).

Algorithm mColoring(k)
{
    repeat 
    {  // Generate all legal assignment of x[k].
        NextValue(k);  // Assign to x[k] a legal color.
         
        if (x[k]=0) then return ;   // No new color possible.
         
        if (k=n)    // At most m colors have been used to color n vertices
            write (x[1:n]);
        else
            mColoring (k+1);
    } untill (false);
}

Algorithm NextValue(k) {
    repeat {  
        x[k]: = (x[k]+1)mod (m+1);  // Next highest color
        if (x[k]=0) then return;    //All colors have been used.
         
        for j:=1 to n do
        {   //check if this color is distant from adjacent colors.
            if ((G[k,j]!=0) and  (x[k]=x[j]))
                //if (k,j ) is an edge and if adj. 
                //vertices have the same color.
                then break;
        }
         
        if(j=n+1) then return;  //New color  found
    }untill (false);    // Try to find another color.
}

Source Code

#include<stdio.h> #include<stdlib.h> void next_value(int **g, int *x, int m, int n, int k) { int j; while (1) { x[k] = (x[k] + 1) % (m + 1); if (x[k] == 0) return; for (j = 1; j <= n; j++) { if (g[k][j] != 0 && (x[k] == x[j])) break; } if (j == n + 1) return; } } void coloring(int **g, int *x, int m, int n, int k) { int i; do { next_value(g, x, m, n, k); if (x[k] == 0) return; if (k == n) { for (i = 1; i <= n; i++) printf("vertex %d = color No. %d\t", i, x[i]); printf("\n"); } else coloring(g, x, m, n, k + 1); } while (k < n + 1); } int main() { int e, k, l; int *x, **g, n, i, j, m; printf("Enter no. of vertices : "); scanf("%d", &n); printf("Enter no. of edges : "); scanf("%d", &e); x = (int *)malloc((n + 1) * sizeof(int)); g = (int **)malloc((n + 1) * sizeof(int *)); for(i = 0; i <= n; i++) g[i] = (int *)malloc((n + 1) * sizeof(int)); m = n - 1; printf("\nThe maximum possible colours that can be assigned are: %d\n", m); for (i = 0; i <= n; i++) for (j = 0; j <= n; j++) g[i][j] = 0; printf("Enter u and v of an edge\n"); for (i = 1; i <= e; i++) { printf("\nfor egde %d\n", i); scanf(" %d %d", &k, &l); g[k][l] = 1; g[l][k] = 1; } for (i = 0; i <= n; i++) x[i] = 0; printf("\nThe colouring possibilities are:\n"); coloring(g, x, m, n, 1); return 0; }

---

Happy Exploring!