M-coloring Problem

Introduction

To study graphs as mathematical structures, we use graph labeling. Graph labeling is a way of assigning labels to vertices, edges, or faces of a graph. It can be done in various ways.

Graph coloring is one of the prime methods of labeling. It is a process of assigning labels or "colors" to elements of a graph following certain constraints.

In this blog, we'll discuss one such problem, known as the M-coloring problem. So, let's get started.

(Also see Data Structures)

Problem Statement

The m-coloring problem states, "We are given an undirected graph and m number of different colors. We have to check if we can assign colors to the vertices of the graphs in such a way that no two adjacent vertices have the same color."

Let’s understand this problem with the help of an example.

Example: Given an adjacency matrix of an undirected graph and a number M having a value of 3.

We've to check if we can color the above four vertices such that no two adjacent vertices have the same color.

After assigning the colors, the graph will look like this.

In this graph, we can see that nodes 2 and 3 are not adjacent and have the same color; the remaining nodes have different colors. This is one possible solution.

Note: The m-coloring problem can have multiple solutions.

There are various ways to solve the M-coloring problem. We’ll be seeing some of them in this article. let’s move on with the brute force approach.

Recommended try the Problem yourself before moving on to the solution

Approach 1: Brute Force

This approach will try to find all the possible combinations in which vertices can be colored. After all the combinations are made, we'll check if it follows the constraints of graph coloring. If the constraints are satisfied, that will be the answer.

The implementation of the above approach is given below:

C++ Implementation

#include<bits/stdc++.h>

using namespace std;

//Number of vertices in the graph
#define V 4

//Function to display
void Display(int color[]) {
  cout << "Solution Exists \n The colors given to vertices are: "<<endl;
  for (int i = 0; i < V; i++)
    cout << "Vertex " << i + 1 << " is given color:" << color[i] << endl;
  cout << endl;
}

//Function to check constraints
bool satisfyConstraints(bool Adj_matrix[V][V], int color[]) {
  for (int i = 0; i < V; i++) {
    for (int j = i + 1; j < V; j++) {
      if (Adj_matrix[i][j] && color[j] == color[i]) {
        return false;
      }
    }
  }
  return true;
}
//Function for m-coloring problem
bool m_Coloring(bool Adj_matrix[V][V], int m, int i, int color[V]) {
  // if current index reached end
  if (i == V) {
    // if constraint is satisfied
    if (satisfyConstraints(Adj_matrix, color)) {
      Display(color);
      return true;
    }
    return false;
  }

  // Assign each color from 1 to m
  for (int j = 1; j <= m; j++) {
    color[i] = j;
    // For the rest of the vertices
    if (m_Coloring(Adj_matrix, m, i + 1, color))
      return true;
    color[i] = 0;
  }

  return false;
}

// Driver code
int main() {
  // The adjacency matrix of the graph
  bool Adj_matrix[V][V] = {
    {0,1,1,1},
    {1,0,0,1},
    {1,0,0,1},
    {1,1,1,0},
  };
  // Number of colors available
  int m = 3;

  // Initialising all vertices with the color values as 0
  int color[V];
  for (int i = 0; i < V; i++) {
    color[i] = 0;
  }

  if (m_Coloring(Adj_matrix, m, 0, color) == 0)
    cout << "No such arrangement exists!!" << endl;

  return 0;
}

Java Implementation

public class Main {
  // Number of vertices in the graph
  static int V = 4;

  /* A utility function to print solution */
  static void display(int[] color) {
    System.out.println("Solution Exists:\n" +
      "The colors given to vertices are: ");
    for (int i = 0; i < V; i++) {
      System.out.println("Vertex " + (i + 1) + " is given color : " + color[i]);
    }
  }

  // check if the colored
  // graph is safe or not
  static boolean isSafe(boolean[][] graph, int[] color) {
    // check for every edge in a graph
    for (int i = 0; i < V; i++)
      for (int j = i + 1; j < V; j++)
        if (graph[i][j] && color[j] == color[i])
          // if matches return false
          return false;
    // if not return true as it is safe
    return true;
  }

  static boolean graphColoring(boolean[][] graph, int m,
    int i, int[] color) {
    // if current index reached end
    if (i == V) {

      // if coloring is safe
      if (isSafe(graph, color)) {

        // Print the solution
        display(color);
        return true;
      }
      return false;
    }

    // Assign each color from 1 to m
    for (int j = 1; j <= m; j++) {
      color[i] = j;

      // Recur of the rest vertices
      if (graphColoring(graph, m, i + 1, color))
        return true;
      color[i] = 0;
    }
    return false;
  }

  public static void main(String[] args) {
    boolean[][] graph = {
      {
        false,
        true,
        true,
        true
      },
      {
        true,
        false,
        true,
        false
      },
      {
        true,
        true,
        false,
        true
      },
      {
        true,
        false,
        true,
        false
      },
    };
    int m = 3; // Number of colors

    // Initialize all color values as 0.
    // This initialization is needed
    // correct functioning of isSafe()
    int[] color = new int[V];
    for (int i = 0; i < V; i++)
      color[i] = 0;
    if (!graphColoring(graph, m, 0, color))
      System.out.println("Solution does not exist");
  }
}

Python Implementation

# Number of vertices in the graph
# define 4 4

# check if the colored
# graph is safe or not
def isSafe(graph, color):

	# check for every edge in the graph
	for i in range(4):
		for j in range(i + 1, 4):
			if (graph[i][j] and color[j] == color[i]):
				return False
	return True

def graphColoring(graph, m, i, color):

	# if current index reached end
	if (i == 4):

		# if coloring is safe
		if (isSafe(graph, color)):

			# Print the solution
			display(color)
			return True
		return False

	# Assign each color from 1 to m
	for j in range(1, m + 1):
		color[i] = j

		# Recur of the rest vertices
		if (graphColoring(graph, m, i + 1, color)):
			return True
		color[i] = 0
	return False

# /* A utility function to print solution */
def display(color):
	print("Solution Exists:" " Following are the assigned colors ")
	for i in range(4):
		print("Vertex", i+1 ," is given color: ",color[i])

# Driver code
if __name__ == '__main__':
	graph = [
		[ 0, 1, 1, 1 ],
		[ 1, 0, 1, 0 ],
		[ 1, 1, 0, 1 ],
		[ 1, 0, 1, 0 ],
	]
	m = 3 # Number of colors

	# Initialize all color values as 0.
	# This initialization is needed
	# correct functioning of isSafe()
	color = [0 for i in range(4)]

	if (not graphColoring(graph, m, 0, color)):
		print ("Solution does not exist")

Output

The colors given to vertices are:
Vertex 1 is given color:1
Vertex 2 is given color:2
Vertex 3 is given color:2
Vertex 4 is given color:3

Complexity Analysis

Time Complexity: O(M^V).

Reason: Choosing out of M given colors for V vertices will lead to an O(M^V) combination. So the time complexity is O(M^V).

Space Complexity: O(V).

Reason: The m_Coloring function will require O(V) space for the recursive call stack.

Approach 2: Backtracking

Backtracking is a general algorithm for solving constraint satisfaction problems. It accomplishes this by constructing a solution incrementally, one component at a time, discarding any solutions that fail to satisfy the problem's criteria at any point in time.

In the above approach, we've seen that we are creating combinations after assigning colors to vertices and then checking the constraints. A different solution to this problem is to only assign colors to a particular vertex if it satisfies the constraints.

We'd assign a color to each vertex from 1 to m and see if it has a different color than its next vertex. If we obtain a configuration in which each node is colored from 1 to m, and adjacent vertices are of different colors, this will be the answer.

Let’s see the implementation of this approach.

C++ Implementation

#include <bits/stdc++.h>

using namespace std;

// Number of vertices in the Adj_matrix
#define V 4

//Function to display
void Display(int color[]) {
  cout << "The colors given to vertices are:" << endl;
  for (int i = 0; i < V; i++)
    cout << "Vertex " << i + 1 << " is given color:" << color[i] << endl;
  cout << endl;
}

//Function to check constraints
bool satisfyConstraints(int v, bool Adj_matrix[V][V], int color[], int c) {
  for (int i = 0; i < V; i++) {
    if (Adj_matrix[v][i] && c == color[i])
      return false;
  }
  return true;
}

/* A recursive utility function
to solve m-coloring problem */
bool m_Coloring_Helper(bool Adj_matrix[V][V], int m, int color[], int v) {

  //If all vertices are assigned a color
  if (v == V)
    return true;

  //Try different colors to vertex v
  for (int c = 1; c <= m; c++) {

    // Check if given color is valid 
    if (satisfyConstraints(v, Adj_matrix, color, c)) {
      color[v] = c;

      //Assign colors to rest of the vertices
      if (m_Coloring_Helper(Adj_matrix, m, color, v + 1) == true)
        return true;

      //Backtrack
      color[v] = 0;
    }
  }

  // If no color can be assigned
  return false;
}

bool m_Coloring(bool Adj_matrix[V][V], int m) {

  // Initialize all color values as 0.
  int color[V];
  for (int i = 0; i < V; i++) {
    color[i] = 0;
  }

  // Call m_Coloring_Helper() for vertex 0
  if (m_Coloring_Helper(Adj_matrix, m, color, 0) == false) {
    cout << "No such arrangement exists!!";
    return false;
  }

  // Print the solution
  Display(color);
  return true;
}

int main() {
  // The adjacency matrix of the graph
  bool Adj_matrix[V][V] = {
    {0,1,1,1},
    {1,0,0,1},
    {1,0,0,1},
    {1,1,1,0},
  };

  // Number of colors
  int m = 3;
  m_Coloring(Adj_matrix, m);
  return 0;
}

Java Implementation

class Main {
  final int V = 4;
  int color[];

  /* A utility function to check
  if the current color assignment
  is safe for vertex v */
  boolean isSafe(
    int v, int graph[][], int color[],
    int c) {
    for (int i = 0; i < V; i++)
      if (
        graph[v][i] == 1 && c == color[i])
        return false;
    return true;
  }

  /* A recursive utility function
  to solve m coloring problem */
  boolean graphColoringUtil(
    int graph[][], int m,
    int color[], int v) {
    /* base case: If all vertices are
    assigned a color then return true */
    if (v == V)
      return true;

    /* Consider this vertex v and try
    different colors */
    for (int c = 1; c <= m; c++) {
      /* Check if assignment of color c to v
      is fine*/
      if (isSafe(v, graph, color, c)) {
        color[v] = c;

        /* recur to assign colors to rest
        of the vertices */
        if (
          graphColoringUtil(
            graph, m,
            color, v + 1))
          return true;

        /* If assigning color c doesn't lead
        to a solution then remove it */
        color[v] = 0;
      }
    }

    /* If no color can be assigned to
    this vertex then return false */
    return false;
  }

  boolean graphColoring(int graph[][], int m) {
    // Initialize all color values as 0. This
    // initialization is needed correct
    // functioning of isSafe()
    color = new int[V];
    for (int i = 0; i < V; i++)
      color[i] = 0;

    // Call graphColoringUtil() for vertex 0
    if (
      !graphColoringUtil(
        graph, m, color, 0)) {
      System.out.println(
        "Solution does not exist");
      return false;
    }

    // display the solution
    display(color);
    return true;
  }

  /* A utility function to print solution */
  void display(int color[]) {
    System.out.println(
      "Solution Exists: Following" +
      " are the assigned colors");
    for (int i = 0; i < V; i++)
      System.out.println(" Vertex " + (i + 1) + " is given color : " + color[i] + " ");
    System.out.println();
  }

  // driver program to test above function
  public static void main(String args[]) {
    Main Coloring = new Main();
    int graph[][] = {{0, 1, 1, 1},{ 1, 0, 1, 0},{1, 1, 0, 1},{1, 0, 1, 0}};
    int m = 3; // Number of colors
    Coloring.graphColoring(graph, m);
  }
}

Python Implementation

# Python program for solution of M Coloring
# problem using backtracking

class Graph():

	def __init__(self, vertices):
		self.V = vertices
		self.graph = [[0 for column in range(vertices)]\
							for row in range(vertices)]

	# A utility function to check
	# if the current color assignment
	# is safe for vertex v
	def isSafe(self, v, colour, c):
		for i in range(self.V):
			if self.graph[v][i] == 1 and colour[i] == c:
			    return False
		return True
	
	# A recursive utility function to solve m
	# coloring problem
	def graphColourUtil(self, m, colour, v):
		if v == self.V:
			return True

		for c in range(1, m + 1):
			if self.isSafe(v, colour, c) == True:
				colour[v] = c
				if self.graphColourUtil(m, colour, v + 1) == True:
				    return True
				colour[v] = 0

	def graphColouring(self, m):
		colour = [0] * self.V
		if self.graphColourUtil(m, colour, 0) == None:
		    return False
		print ("Solution exist and Following are the assigned colours:")
		for i in range(4):
		    print("Vertex", i+1, "is given color: ",colour[i])
		return True

# Driver Code
g = Graph(4)
g.graph = [[0, 1, 1, 1], [1, 0, 1, 0], [1, 1, 0, 1], [1, 0, 1, 0]]
m = 3
g.graphColouring(m)

Output

The colors given to vertices are:
Vertex 1 is given color:1
Vertex 2 is given color:2
Vertex 3 is given color:2
Vertex 4 is given color:3

Complexity Analysis

Time Complexity: O(M^V).

Reason: Choosing out of M given colors for V vertices will lead to an O(M^V) combination. So the time complexity is O(M^V).

Space Complexity: O(V).

Reason: The M_Coloring function will require O(V) space for the recursive call stack.

The above two approaches have the same time complexity regardless of different algorithms. In our next approach, we’ll be discussing an optimal approach to solve the M-coloring problem.

Approach 3: Breadth-First Search

In this approach, first of all, we’ll color all the vertices of the graph with the first color. Then we’ll traverse the graph in a breadth-first fashion starting from the first unvisited node.

After reaching a node, we’ll check the color of all the adjacent nodes of the current node. If the current and the adjacent node have the same color, we’ll assign the next color to the adjacent node. Mark the current node as visited and move forward.

Let’s see the algorithm of this approach.

Step 1: Start the BFS traversal.

Step 2: Find out the neighboring (adjacent) nodes of the current node.

If the color of the current node and the adjacent node is the same, assign the next color to the adjacent node.
Check if the current node has been visited or not. Mark it as visited and add it to a queue if it hasn't been visited yet.

Step 3: Check the condition for color availability. If the condition becomes false, return.

Step 4: Do it for all the given nodes.

C++ Implementation

#include <bits/stdc++.h>

using namespace std;

// Number of vertices in the Adj_matrix
#define V 4

//Function to display
void Display(int color[]) {
  cout << "The colors given to vertices are:" << endl;
  for (int i = 0; i < V; i++)
    cout << "Vertex " << i + 1 << " is given color:" << color[i] << endl;
  cout << endl;
}

//Function to check constraints
bool satisfyConstraints(int v, bool Adj_matrix[V][V], int color[], int c) {
  for (int i = 0; i < V; i++) {
    if (Adj_matrix[v][i] && c == color[i])
      return false;
  }
  return true;
}

/* A recursive utility function
to solve m-coloring problem */
bool m_Coloring_Helper(bool Adj_matrix[V][V], int m, int color[], int v) {

  //If all vertices are assigned a color
  if (v == V)
    return true;

  //Try different colors to vertex v
  for (int c = 1; c <= m; c++) {

    // Check if given color is valid 
    if (satisfyConstraints(v, Adj_matrix, color, c)) {
      color[v] = c;

      //Assign colors to rest of the vertices
      if (m_Coloring_Helper(Adj_matrix, m, color, v + 1) == true)
        return true;

      //Backtrack
      color[v] = 0;
    }
  }

  // If no color can be assigned
  return false;
}

bool m_Coloring(bool Adj_matrix[V][V], int m) {

  // Initialize all color values as 0.
  int color[V];
  for (int i = 0; i < V; i++) {
    color[i] = 0;
  }

  // Call m_Coloring_Helper() for vertex 0
  if (m_Coloring_Helper(Adj_matrix, m, color, 0) == false) {
    cout << "No such arrangement exists!!";
    return false;
  }

  // Print the solution
  Display(color);
  return true;
}

int main() {
  // The adjacency matrix of the graph
  bool Adj_matrix[V][V] = {
    {0,1,1,1},
    {1,0,0,1},
    {1,0,0,1},
    {1,1,1,0},
  };

  // Number of colors
  int m = 3;
  m_Coloring(Adj_matrix, m);
  return 0;
}

Java Implementation

// Java Implementation
import java.io.*;
import java.util.*;
class Node {

  // A node class which stores the color and the edges connected to the node
  int color = 1;
  Set < Integer > edges = new HashSet < Integer > ();
}
public class mColoring {
  static int possiblePaint(ArrayList < Node > nodes, int n, int m) {

    // Create a visited array of n nodes
    ArrayList < Integer > visited = new ArrayList < Integer > ();
    // initialized to zero
    for (int i = 0; i < n + 1; i++) {
      visited.add(0);
    }

    // maxColors used till now are 1 as
    // all nodes are painted color 1
    int maxColors = 1;

    // Do a full BFS traversal from
    // all unvisited starting points
    for (int sv = 1; sv <= n; sv++) {
      if (visited.get(sv) > 0) {
        continue;
      }

      // If the starting point is unvisited,
      // mark it visited and push it in queue
      visited.set(sv, 1);
      Queue < Integer > q = new LinkedList < > ();
      q.add(sv);

      // BFS Travel starts here
      while (q.size() != 0) {
        int top = q.peek();
        q.remove();

        // Checking all adjacent nodes
        // to "top" edge in our queue
        for (int it: nodes.get(top).edges) {

          // IMPORTANT: If the color of the
          // adjacent node is same, increase it by 1
          if (nodes.get(top).color == nodes.get(it).color) {
            nodes.get(it).color += 1;
          }

          // If number of colors used shoots m, return
          // 0
          maxColors = Math.max(maxColors,
            Math.max(nodes.get(top).color,
              nodes.get(it).color));
          if (maxColors > m)
            return 0;

          // If the adjacent node is not visited,
          // mark it visited and push it in queue
          if (visited.get(it) == 0) {
            visited.set(it, 1);
            q.remove(it);
          }
        }

      }
    }
    return 1;
  }

  // Driver code
  public static void main(String[] args) {
    int n = 4;
     int [][] graph = {{ 0, 1, 1, 1 },{ 1, 0, 1, 0 },{ 1, 1, 0, 1 },{ 1, 0, 1, 0 }};
    int m = 3; // Number of colors

    // Create a vector of n+1
    // nodes of type "node"
    // The zeroth position is just
    // dummy (1 to n to be used)
    ArrayList < Node > nodes = new ArrayList < Node > ();

    for (int i = 0; i < n + 1; i++) {
      nodes.add(new Node());
    }

    // Add edges to each node as per given input
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (graph[i][j] > 0) {
          // Connect the undirected graph
          nodes.get(i).edges.add(i);
          nodes.get(j).edges.add(j);
        }
      }
    }

    // Display answer
    int res = possiblePaint(nodes, n, m);
    if (res == 1) {
      System.out.println("It is possible to color all the nodes!!");
    } else {
      System.out.println("No solution exists!!");
    }
  }
}

Python Implementation

# Python Implementation
from queue import Queue

class node:
	
	color = 1
	edges = set()

def possiblePaint(nodes, n, m):

	# Create a visited array of n
	# nodes, initialized to zero
	visited = [0 for _ in range(n+1)]

	# maxColors used till now are 1 as
	# all nodes are painted color 1
	maxColors = 1

	# Do a full BFS traversal from
	# all unvisited starting points
	for _ in range(1, n + 1):
		if visited[_]:
			continue

		# If the starting point is unvisited,
		# mark it visited and push it in queue
		visited[_] = 1
		q = Queue()
		q.put(_)

		# BFS Travel starts here
		while not q.empty():
			top = q.get()

			# Checking all adjacent nodes
			# to "top" edge in our queue
			for _ in nodes[top].edges:

				# IMPORTANT: If the color of the
				# adjacent node is same, increase it by 1

				if nodes[top].color == nodes[_].color:
					nodes[_].color += 1

				# If number of colors used shoots m,
				# return 0
				maxColors = max(maxColors, max(
					nodes[top].color, nodes[_].color))
					
				if maxColors > m:
					print(maxColors)
					return 0

				# If the adjacent node is not visited,
				# mark it visited and push it in queue
				if not visited[_]:
					visited[_] = 1
					q.put(_)
					
	return 1

# Driver code
if __name__ == "__main__":
	
	n = 4
	graph = [ [ 0, 1, 1, 1 ],
			[ 1, 0, 1, 0 ],
			[ 1, 1, 0, 1 ],
			[ 1, 0, 1, 0 ] ]
	m = 3
	nodes = []
	for _ in range(n+1):
		nodes.append(node())

	# Add edges to each node as
	# per given input
	for _ in range(n):
		for __ in range(n):
			if graph[_][__]:
				
				# Connect the undirected graph
				nodes[_].edges.add(_)
				nodes[__].edges.add(__)

	# Display the final answer
	ans = possiblePaint(nodes, n, m)
	if(ans == 1):
	    print("It is possible to color all the nodes!!")
	else:
	    print("No solution exists!!")

Output

It is possible to color all the nodes!!

Complexity Analysis

Time Complexity: O(V + E).

Reason: The time complexity of BFS traversal is O(V). For every node, we are checking all its adjacent nodes, this will lead to the time complexity of O(V + E).

Space Complexity: O(V).

Reason: The M_coloring function will require O(V) space for the visited array.

Frequently Asked Questions

What is Graph Coloring?

Graph coloring is an important problem of graph theory. In this problem, we'll be given a graph to color all of the vertices with the 'm' colors provided, ensuring that no two neighboring vertices have the same color.

What do you mean by the M-coloring decision problem?

The smallest number m for which the graph G can be colored is the M – colorability optimization problem. The integer is referred to as the graph's chromatic Number.

What are the applications of graph coloring?

There are various graph coloring applications, such as creating a schedule, register allocation, and Mobile Radio Frequency Assignment.

Conclusion

In this article, we discussed the graph coloring problem and some approaches to how to solve it in detail. Graph coloring is one of the most frequently asked and important concepts in graph theory.

To get a clear insight into graph theory fundamentals, we suggest you go through this fantastic article. If you have any difficulty understanding the graph representation in the above-given approaches, here's a blog to get you acquainted with the types and representation of graphs.