Graph Coloring Problem

Graph Coloring Problem

Problem Statement

Graph coloring problem involves assigning colors to certain elements of a graph subject to certain restrictions and constraints. In other words, the process of assigning colors to the vertices such that no two adjacent vertexes have the same color is caller Graph Colouring.

This is also known as vertex coloring.

Example:

Confused about your next job?

In 3 simple steps you can find your personalised career roadmap in Software development for FREE



Expand in New Tab 

 

Chromatic Number:  The smallest number of colours needed to colour a graph G is called its chromatic number.

For example, in the above image, vertices can be coloured using a minimum of 2 colours.

Hence the chromatic number of the graph is 2. 

Further examples for a more clear understanding:

Applications of Graph Colouring:

  • Map Coloring
  • Scheduling the tasks
  • Preparing Time Table
  • Assignment
  • Conflict Resolution
  • Sudoku

Approach 1: Brute Force

  • The simplest approach to solve this problem would be to generate all possible combinations (or configurations) of colours.
  • After generating a configuration, check if the adjacent vertices have the same colour or not. If the conditions are met, add the combination to the result and break the loop.
  • Since each node can be coloured by using any of the M colours, the total number of possible colour configurations are mV. The complexity is exponential which is very huge.

C++ Implementation

bool isSafeToColor(vector < vector < int >> & graph, vector < int > color) {
  for (int i = 0; i < V; i++)
    for (int j = i + 1; j < V; j++)
      if (graph[i][j] == 1 && color[j] == color[i])
        return false;
  return true;
}
 
void printColorArray(vector < int > color) {
  cout << ("Solution colors are: ") << endl;
  for (int i = 0; i < color.size(); i++) {
    cout << (color[i]);
  }
}
bool graphColoring(vector < vector < int >> & graph, int m, int i, vector < int > color) {
  if (i == V) {
    if (isSafeToColor(graph, color)) {
      printColorArray(color);
      return true;
    }
    return false;
  }
  for (int j = 1; j <= m; j++) {
    color[i] = j;
    if (graphColoring(graph, m, i + 1, color))
      return true;
 
    color[i] = 0;
  }
 
  return false;
}

Java Implementation

private static boolean isSafeToColor(int[][] graph, int[] color) {
  for (int i = 0; i < V; i++)
    for (int j = i + 1; j < V; j++)
      if (graph[i][j] == 1 && color[j] == color[i])
        return false;
  return true;
}
 
private static void printColorArray(int[] color) {
  System.out.println("Solution colors are: ")
  for (int i = 0; i < color.length; i++) {
    System.out.println(color[i]);
  }
}
private static boolean graphColoring(int[][] graph, int m, int i, int[] color) {
  if (i == V) {
    if (isSafeToColor(graph, color)) {
      printColorArray(color);
      return true;
    }
    return false;
  }
  for (int j = 1; j <= m; j++) {
    color[i] = j;
    if (graphColoring(graph, m, i + 1, color))
      return true;
 
    color[i] = 0;
  }
 
  return false;
}

Python Implementation

def isSafeToColor(graph, color):
    for i in range(V):
        for j in range(i + 1, V):
            if graph[i][j] == 1 and color[j] == color[i]:
                return False
    return True
 
 
def printColorArray(color):
    print("Solution colors are: ")
    for i in range(len(color)):
        print(color[i], end=" ")
 
 
def graphColoring(graph, m, i, color):
    if i == V:
        if isSafeToColor(graph, color):
            printColorArray(color)
            return True
        return False
 
    for j in range(1, m + 1):
        color[i] = j
        if graphColoring(graph, m, i + 1, color):
            return True
 
        color[i] = 0
 
    return false

Time Complexity:O(M^V), where M is the total colors needed and V is total vertices
Space Complexity:O(V), as extra space is used for coloring vertices.

Approach 2: Backtracking

In the previous approach, trying and checking every possible combination was tedious and had an exponential time complexity.
Some of the permutation calculations were unnecessary but were calculated again and again. Therefore, the idea is to use a backtracking approach to solve the problem.

In this approach, the idea is to color a vertex and while coloring any adjacent vertex, choose a different color. Similarly, color every possible vertex following the restrictions, till any further vertex is left coloring. In any case, if all adjacent vertices for a given vertex are colored, then backtrack and change color.

If after coloring, if we return back to the same vertex that was started with and all colors are used, then more colors are needed. Hence, return False.

Algorithm

  • Consider a color and check if it is valid i.e. from the given vertex check whether its adjacent vertices have been coloured with the same color.
  • If true, pick a different colour, else continue colouring the vertices.
  • If no other color is left un-used, then backtrack.

C++ Code

class InterviewBit {
  public:
    int V = 4;
 
  bool isSafeToColor(int v, vector < vector < int >> & graphMatrix, vector < int > color, int c) {
    for (int i = 0; i < V; i++)
      if (graphMatrix[v][i] == 1 && c == color[i])
        return false;
    return true;
  }
 
  bool graphColorUtil(vector < vector < int >> & graphMatrix, int m, vector < int > color, int v) {
    if (v == V)
      return true;
 
    for (int i = 1; i <= m; i++) {
      if (isSafeToColor(v, graphMatrix, color, i)) {
        color[v] = i;
        if (graphColorUtil(graphMatrix, m, color, v + 1))
          return true;
        color[v] = 0;
      }
    }
    return false;
  }
 
  void printColoringSolution(int color[]) {
    cout << ("Color schema for vertices are: ") << endl;
    for (int i = 0; i < V; i++)
      cout << (color[i]) << endl;
  }
  bool graphColoring(vector < vector < int >> & graphMatrix, int m) {
    vector < int > color(V, 0);
 
    if (!graphColorUtil(graphMatrix, m, color, 0)) {
      cout << "Color schema not possible" << endl;
      return false;
    }
 
    printColoringSolution(color);
    return true;
  }

Java Code

public class InterviewBit {
        final int V = 4;
        int[] color;
        
        boolean isSafeToColor(int v, int[][] graphMatrix, int[] color, int c)
        {
            for (int i = 0; i < V; i++)
                if (graphMatrix[v][i] == 1 && c == color[i])
                    return false;
            return true;
        }
 
        boolean graphColorUtil(int[][] graphMatrix, int m, int[] color, int v)
        {
            if (v == V)
                return true;
 
            for (int i = 1;i <= m; i++) 
            {
                if (isSafeToColor(v, graphMatrix, color, i))
                {
                    color[v] =i;
                    if (graphColorUtil(graphMatrix, m, color, v + 1))
                        return true;
                    color[v] = 0;
                }
            }
            return false;
        }
 
        void printColoringSolution(int color[])
        {
            System.out.println("Color schema for vertices are: ");
            for (int i = 0; i < V; i++)
                System.out.println(color[i]);
        }
        boolean graphColoring(int[][] graphMatrix, int m)
        {
            color = new int[V];
            Arrays.fill(color,0);
 
            if (!graphColorUtil(graphMatrix, m, color, 0)) 
            {
                System.out.println(
                    "Color schema not possible");
                return false;
            }
 
            printColoringSolution(color);
            return true;
        }

Python Code

class InterviewBit:
    V = 4;
        
    def isSafeToColor(v, graphMatrix, color, c):
        for i in range(V):
            if graphMatrix[v][i] == 1 and c == color[i]:
                return False;
        return True;
 
    def graphColorUtil(graphMatrix, m, color, v):
        
        if v == V:
            return True;
 
        for i in range(1, m + 1):
            if isSafeToColor(v, graphMatrix, color, i):
                color[v] =i;
                if graphColorUtil(graphMatrix, m, color, v + 1):
                    return True;
                color[v] = 0;
                
        return false;
 
    def printColoringSolution(color):
        print("Color schema for vertices are: ")
        for i in range(V):
            print(color[i])
    def graphColoring(graphMatrix, m):
        
        color = [0]*(V)
 
        if !graphColorUtil(graphMatrix, m, color, 0):
            print("Color schema not possible")
            return False;
 
        printColoringSolution(color);
        return True;

Time Complexity:O(M^V), in the worst case.
Space Complexity:O(V), as extra space is used for coloring vertices.

FAQs

What is Chromatic Number
The smallest number of colors needed to color a graph G is called its chromatic number.

What does the backtracking approach have the same time complexity as the brute force approach?
The backtracking approach is also a type of brute force. It is just used to eliminate bad decisions while coloring the vertices.

Previous Post
Reverse String

Reverse String (C++, Java, and Python)

Next Post
Subarray Sum Equals K

Subarray Sum Equals K

Total
0
Share