Graph Coloring

What is Graph Coloring Problem?

We have been given a graph and is asked to color all vertices with ‘m‘ given colors in such a way that no two adjacent vertices should have the same color. This graph coloring problem is also known as M-colorability decision problem.

The M – colorability optimization problem deals with the smallest integer m for which the graph G can be colored. The integer is known as a chromatic number of the graph.

The least possible value of ‘m‘ required to color the graph successfully is known as the chromatic number of the given graph.

Let’s understand and how to solve graph coloring problem?

Graph Coloring Algorithm

Naive Algorithm

In this approach we first find all permutations of colors possible to color every vertex of the graph using Brute Force Method. Clearly if there is a large number of vertices, more the time it will take.

Bactracking Algorithm

Backtracking algorithm makes the process to solve the problem more efficient by avoiding much bad decision that needed to be made in the naive approach.

We start by coloring a single vertex, then we move to its adjacent vertex. We color it with that color which has not been used to color any of its connected vertices. After coloring it we then move to its adjacent vertex which is uncolored. We repeat the process until all vertices of the given graph are colored.

In case we find for a vertex that all its adjacent (connected) are colored with different colors and no color is left to make it color different from them, then it means the given number of colors i.e ‘m’, is insufficient to color the graph. Hence we require more colors i.e bigger chromatic number.

Steps To Color Graph Using Backtracking Algorithm

1. Confirm whether it is valid to color the vertex with current color? by checking whether any of its adjacent vertices are colored with the same color?
2. If yes then color it or else try with another color.
3. If no other color is available then backtrack i.e un-color last colored vertex and return false.
4. After each coloring check if all vertices are colored or not. If yes then end the program by returning true, else continue.
5. Now select any one of the uncolored adjacent vertices of the current colored vertex and repeat the whole process

Here backtracking means to stop further recursive calls on adjacent vertices by returning false. In this algorithm Step-2 (Continue) and Step-4 (backtracking) is causing the program to try different color option.

Continue – try a different color for current vertex.
Backtrack – try a different color for last colored vertex

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
//Number of vertices
#define numOfVertices 4
 
//function Prototypes
bool canColorWith(int , int );
 
// 0 - Green
// 1 - Blue
 
char colors[][30] = {"Green","Blue"};
int color_used = 2;
int colorCount;
 
//Graph connections
int graph[numOfVertices][numOfVertices] =  {{0, 1, 0, 1},
                                            {1, 0, 1, 0},
                                            {0, 1, 0, 1},
                                            {1, 0, 1, 0}};
 
typedef struct{
    char name;
    bool colored;
    int color;
 
} Vertex;
 
//VertexList
Vertex *vertexArray[numOfVertices];
 
int hasUncoloredNeighbours(int idx){
    int i;
    for(i=0;i<numOfVertices; i++){
         if(graph[idx][i] == 1 && vertexArray[i]->colored == false)
            return i;
    }
    return -1;
}
 
bool setColors(int idx){
 
    int colorIndex, unColoredIdx;
 
        for (colorIndex=0; colorIndex<color_used; colorIndex++){
 
            // Step-1 : checking validity
            if(!canColorWith(colorIndex, idx)) continue;  //Step-2 : Continue
 
            //Step-2 : coloring
            vertexArray[idx]->color =  colorIndex;
            vertexArray[idx]->colored = true;
            colorCount++;
 
            //Step-4 : Whether all vertices colored?
            if(colorCount == numOfVertices ) //Base Case
                return true;
 
            //Step-5 : Next uncolored vertex
            while((unColoredIdx = hasUncoloredNeighbours(idx)) != -1){
                    if(setColors(unColoredIdx))
                        return true;
            }
 
        }
 
        // Step-3 : Backtracking
        vertexArray[idx]->color = -1;
        vertexArray[idx]->colored = false;
        return false;
}
 
//Function to check whether it is valid to color with color[colorIndex]
 bool canColorWith(int colorIndex, int vertex) {
    Vertex *neighborVertex;
    int i;
 
    for(i=0; i<numOfVertices; i++){
 
        //skipping if vertex are not connected
        if(graph[vertex][i] == 0) continue;
 
        neighborVertex = vertexArray[i];
        if(neighborVertex->colored && neighborVertex->color == colorIndex)
            return  false;
    }
 
    return true;
}
 
 
int main()
{
    int i;
 
    //Creating Vertex
    Vertex vertexA, vertexB, vertexC, vertexD;
 
    vertexA.name = 'A';
    vertexB.name = 'B';
    vertexC.name = 'C';
    vertexD.name = 'D';
 
    vertexArray[0] = &vertexA;
    vertexArray[1] = &vertexB;
    vertexArray[2] = &vertexC;
    vertexArray[3] = &vertexD;
 
    for(i=0; i<numOfVertices;i++){
        vertexArray[i]->colored = false;
        vertexArray[i]->color = -1;
    }
 
    bool hasSolution = setColors(0);
 
    if (!hasSolution)
        printf("No Solution");
    else {
        for(i=0; i<numOfVertices;i++){
            printf("%c %s \n",vertexArray[i]->name,colors[vertexArray[i]->color]);
        }
    }
 
    return 0;
}

Note: For backtracking, we are returning false to rerun last recursive call to change the color of the last colored vertex. If false is returned by the starting vertex then it means there is no solution.

Complexity Analysis:

• Time Complexity: O(m^V).
  There are total O(m^V) combination of colors. So time complexity is O(m^V). The upperbound time complexity remains the same but the average time taken will be less.
• Space Complexity: O(V).
  To store the output array O(V) space is required.