Algorithm
-
Getting Started with AlgorithmWhat is an Algorithm?
-
Characteristics of Algorithm1 Topic
-
Analysis Framework
-
Performance Analysis3 Topics
-
Mathematical Analysis2 Topics
-
Sorting AlgorithmSorting Algorithm10 Topics
-
Searching Algorithm6 Topics
-
Fundamental of Data StructuresStacks
-
Queues
-
Graphs
-
Trees
-
Sets
-
Dictionaries
-
Divide and ConquerGeneral Method
-
Binary Search
-
Recurrence Equation for Divide and Conquer
-
Finding the Maximum and Minimum
-
Merge Sort
-
Quick Sort
-
Stassen’s Matrix Multiplication
-
Advantages and Disadvantages of Divide and Conquer
-
Decrease and ConquerInsertion Sort
-
Topological Sort
-
Greedy MethodGeneral Method
-
Coin Change Problem
-
Knapsack Problem
-
Job Sequencing with Deadlines
-
Minimum Cost Spanning Trees2 Topics
-
Single Source Shortest Paths1 Topic
-
Optimal Tree Problem1 Topic
-
Transform and Conquer Approach1 Topic
-
Dynamic ProgrammingGeneral Method with Examples
-
Multistage Graphs
-
Transitive Closure1 Topic
-
All Pairs Shortest Paths6 Topics
-
BacktrackingGeneral Method
-
N-Queens Problem
-
Sum of Subsets problem
-
Graph Coloring
-
Hamiltonian Cycles
-
Branch and Bound2 Topics
-
0/1 Knapsack problem2 Topics
-
NP-Complete and NP-Hard Problems1 Topic
Participants2253
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
- 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?
- If yes then color it or else try with another color.
- If no other color is available then backtrack i.e un-color last colored vertex and return false.
- After each coloring check if all vertices are colored or not. If yes then end the program by returning true, else continue.
- 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.