# 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)**.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.