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

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Sieve of Eratosthenes to find prime numbers
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Jump Search Implementation using C++
- Optimal Merge Pattern (Algorithm and Example)
- Introduction to Greedy Strategy in Algorithms
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Graph coloring problem's solution using backtracking algorithm
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- P and NP problems and solutions | Algorithms
- Travelling Salesman Problem
- 2 – 3 Trees Algorithm
- Kruskal's (P) and Prim's (K) Algorithms
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Midpoint Circle Algorithm
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking

Comments and Discussions!