Home » Algorithms

Graph coloring problem’s solution using backtracking algorithm

In this article, we are going to learn about the graph coloring problem and how it can be solved with the help of backtracking algorithm.
Submitted by Shivangi Jain, on July 17, 2018

Graph coloring

The graph coloring problem is to discover whether the nodes of the graph G can be covered in such a way, that no two adjacent nodes have the same color yet only m colors are used. 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.

Here, it can also be noticed that if d is the degree of the given graph, then it can be colored with d+ 1 color.

A graph is also known to be planar if and only if it can be drawn in a planar in such a way that no two edges cross each other. A special case is the 4 - colors problem for planar graphs. The problem is to color the region in a map in such a way that no two adjacent regions have the same color. Yet only four colors are needed. This is a problem for which graphs are very useful because a map can be easily transformed into a graph. Each region of the map becomes the node, and if two regions are adjacent, they are joined by an edge.

Graph coloring problem can also be solved using a state space tree, whereby applying a backtracking method required results are obtained.

For solving the graph coloring problem, we suppose that the graph is represented by its adjacency matrix G[ 1:n, 1:n], where, G[ i, j]= 1 if (i, j) is an edge of G, and G[i, j] = 0 otherwise.

The colors are represented by the integers 1, 2, ..., m and the solutions are given by the n-tuple (x1, x2, x3, ..., xn), where x1 is the color of node i.

Algorithm for finding the m - colorings of a graph

1.	Algorithm mcoloring ( k )
2.	// this algorithm is formed using the recursive backtracking 
3.	// schema. The graph is represented by its Boolean adjacency 
4.	// matrix G [1: n, 1: n]. All assignments of 1, 2, …, m to the 
5.	// vertices of the graph such that adjacent vertices are
6.	// assigned distinct are printed. K is the index 
7.	// of the next vertex to color.
8.	{
9.	Repeat
10.	{
11.	// generate all legal assignments for x[k],
12.	Next value (k); // assign to x[k] a legal color.
13.	 If ( x[k] = 0 ) then return; // no new color possible
14.	 If (k = n) then // at most m colors have been used to color the n vertices.
15.	  Write (x[1 : n ]);
16.	 Else mcoloring (k + 1);
17.	}
18.	Until (false);
19.	}

This algorithm uses the recursive backtracking schema. In this algorithm colors to be assigned are to determine from the range (0, m), i.e., m colors are available.

The total time required by the above algorithm is O (nm^n).