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.

Graph coloring problem

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. Cleary 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.

Graph coloring problem algorithm

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.

Graph Coloring Problem in C | Java using Backtracking

C

Java

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.

Output

graph coloring problem using backtracking example-min

In the program, we have created the same graph as depicted in the first picture and successfully colored the graph using the backtracking algorithm.

This Post Has 2 Comments

  1. Hello,

    I am learning the graph algorithm and I liked your program very much.
    I have GitHub Repository that contains my learning and study on the topic.
    Can I have include your program on my GitHub Repository with the link as the reference and the author within my program?

    1. Ok

Leave a Reply

Close Menu