1.
Introduction
2.
What is M-Coloring problem?
3.
m Coloring Problem Statement
4.
Approach 1: Brute Force
4.1.
C++ Implementation
4.2.
C++
4.3.
Java Implementation
4.4.
java
4.5.
Python Implementation
4.6.
Python
4.7.
Complexity Analysis
5.
Approach 2: Backtracking
5.1.
C++ Implementation
5.2.
C++
5.3.
Java Implementation
5.4.
java
5.5.
Python Implementation
5.6.
Python
5.7.
Complexity Analysis
6.
6.1.
C++ Implementation
6.2.
C++
6.3.
Java Implementation
6.4.
java
6.5.
Python Implementation
6.6.
Python
6.7.
Complexity Analysis
7.
7.1.
What is Graph Coloring?
7.2.
Is M coloring problem backtracking?
7.3.
What is K coloring problem?
7.4.
What is M coloring of a graph?
7.5.
What is the concept of map coloring?
8.
Conclusion
8.1.
Last Updated: Mar 27, 2024
Medium

# M Coloring Problem

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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

## What is M-Coloring problem?

The M-coloring problem is a graph theory problem that involves finding a way to color the vertices of a graph with M colors, such that no two adjoining vertices have the same color. The goal is to allocate colors to the vertices of a graph in such a way that no two neighbouring vertices have the same color, while using the minimum possible number of colors.

The M-coloring problem is known to be NP-complete, which implies that there exists no known algorithm to actually solve it. However, there are various approximation algorithms that can be used to find a good solution to the problem.

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## m Coloring 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++

### C++

``#include<bits/stdc++.h>using namespace std;#define V 4void Display(int color[]) {    cout << "Solution Exists\nThe 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;}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;}bool m_Coloring(bool Adj_matrix[V][V], int m, int i, int color[V]) {    if (i == V) {        if (satisfyConstraints(Adj_matrix, color)) {            Display(color);            return true;        }        return false;    }    for (int j = 1; j <= m; j++) {        color[i] = j;        if (m_Coloring(Adj_matrix, m, i + 1, color)) {            return true;        }    }    return false;}int main() {    bool Adj_matrix[V][V] = {        {0,1,1,1},        {1,0,0,1},        {1,0,0,1},        {1,1,1,0},    };    int m = 3;    int color[V];    for (int i = 0; i < V; i++) {        color[i] = 0;    }    if (!m_Coloring(Adj_matrix, m, 0, color))        cout << "No such arrangement exists!!" << endl;    return 0;}``

• java

### java

``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, int v, int c) {        // check for every vertex in the graph        for (int i = 0; i < V; i++) {            if (graph[v][i] && color[i] == c) {                // if there's an edge and the colors match, return false                return false;            }        }        // if no conflicts, return true        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, i - 1, color[i - 1])) {                // 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 for 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 for the 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

### Python

``# Number of vertices in the graph# define 4 4# check if the colored# graph is safe or notdef isSafe(graph, color):# check for every edge in the graphfor i in range(4):for j in range(i + 1, 4):if (graph[i][j] and color[j] == color[i]):return Falsereturn Truedef graphColoring(graph, m, i, color):# if current index reached endif (i == 4):# if coloring is safeif (isSafe(graph, color)):# Print the solutiondisplay(color)return Truereturn False# Assign each color from 1 to mfor j in range(1, m + 1):color[i] = j# Recur of the rest verticesif (graphColoring(graph, m, i + 1, color)):return Truecolor[i] = 0return 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 codeif __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++

### C++

``#include <bits/stdc++.h>using namespace std;// Number of vertices in the Adj_matrix#define V 4// Function to displayvoid 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 constraintsbool 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 problembool 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 for vertex v    for (int c = 1; c <= m; c++) {        // Check if the given color is valid        if (satisfyConstraints(v, Adj_matrix, color, c)) {            color[v] = c;            // Recursively assign colors to the 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

### java

``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) {        if (v == V) {            return true;        }        for (int c = 1; c <= m; c++) {            if (isSafe(v, graph, color, c)) {                color[v] = c;                if (graphColoringUtil(graph, m, color, v + 1)) {                    return true;                }                color[v] = 0;            }        }        return false;    }    boolean graphColoring(int graph[][], int m) {        color = new int[V];        for (int i = 0; i < V; i++) {            color[i] = 0;        }        if (!graphColoringUtil(graph, m, color, 0)) {            System.out.println("Solution does not exist");            return false;        }        display(color);        return true;    }    /* A utility function to print solution */    void display(int color[]) {        System.out.println("The colors given to vertices are:");        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

### Python

``class Graph:    def __init__(self, vertices):        self.V = vertices        self.graph = [[0 for column in range(vertices)] for row in range(vertices)]    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    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):                colour[v] = c                if self.graphColourUtil(m, colour, v + 1):                    return True                colour[v] = 0    def graphColouring(self, m):        colour = [0] * self.V        if not self.graphColourUtil(m, colour, 0):            print("Solution does not exist")            return False        print("Solution exists, and the assigned colors are:")        for i in range(self.V):            print("Vertex", i + 1, "is given color:", colour[i])        return True# Driver Codeg = Graph(4)g.graph = [    [0, 1, 1, 1],    [1, 0, 1, 0],    [1, 1, 0, 1],    [1, 0, 1, 0]]m = 3g.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.

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++

### C++

``#include <bits/stdc++.h>using namespace std;// Number of vertices in the Adj_matrix#define V 4// Function to displayvoid 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 constraintsbool 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 problembool 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 for vertex v    for (int c = 1; c <= m; c++) {        // Check if the given color is valid        if (satisfyConstraints(v, Adj_matrix, color, c)) {            color[v] = c;            // Recursively assign colors to the 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

### java

``import java.io.*;import java.util.*;class Node {    int color = 1;    Set<Integer> edges = new HashSet<>();}public class mColoring {    static int possiblePaint(ArrayList<Node> nodes, int n, int m) {        ArrayList<Integer> visited = new ArrayList<>();        for (int i = 0; i <= n; i++) {            visited.add(0);        }        int maxColors = 1;        for (int sv = 1; sv <= n; sv++) {            if (visited.get(sv) > 0) {                continue;            }            visited.set(sv, 1);            Queue<Integer> q = new LinkedList<>();            q.add(sv);            while (!q.isEmpty()) {                int top = q.poll();                for (int it : nodes.get(top).edges) {                    if (nodes.get(top).color == nodes.get(it).color) {                        nodes.get(it).color += 1;                    }                    maxColors = Math.max(maxColors, Math.max(nodes.get(top).color, nodes.get(it).color));                    if (maxColors > m) {                        return 0;                    }                    if (visited.get(it) == 0) {                        visited.set(it, 1);                        q.add(it);                    }                }            }        }        return 1;    }    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;        ArrayList<Node> nodes = new ArrayList<>();        for (int i = 0; i <= n; i++) {            nodes.add(new Node());        }        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (graph[i][j] > 0) {                    nodes.get(i + 1).edges.add(j + 1);                    nodes.get(j + 1).edges.add(i + 1);                }            }        }        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

### Python

``from queue import Queueclass Node:    def __init__(self):        self.color = 1        self.edges = set()def possiblePaint(nodes, n, m):    visited = [0 for _ in range(n+1)]    maxColors = 1    for i in range(1, n + 1):        if visited[i]:            continue        visited[i] = 1        q = Queue()        q.put(i)        while not q.empty():            top = q.get()            for neighbor in nodes[top].edges:                if nodes[top].color == nodes[neighbor].color:                    nodes[neighbor].color += 1                maxColors = max(maxColors, max(nodes[top].color, nodes[neighbor].color))                if maxColors > m:                    print(maxColors)                    return 0                if not visited[neighbor]:                    visited[neighbor] = 1                    q.put(neighbor)    return 1if __name__ == "__main__":    n = 4    graph = [        [0, 1, 1, 1],        [1, 0, 1, 0],        [1, 1, 0, 1],        [1, 0, 1, 0]    ]    m = 3    nodes = [Node() for _ in range(n+1)]    for i in range(n):        for j in range(n):            if graph[i][j]:                nodes[i+1].edges.add(j+1)                nodes[j+1].edges.add(i+1)    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.

You can also read How to Solve 8 Queens Problem Using Backtracking.

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

### Is M coloring problem backtracking?

Backtracking is a process which involves solving by trying and testing all possible outcome combinations. If one approach doesn't derive a desired outcome, it backtracks to the previous step and tries a different approach. So yes,  M colouring problem involves a backtracking algorithm.

### What is K coloring problem?

The K coloring problem is a graph theory problem that involves finding a way to color the vertices of a graph with K colors, such that no edges of a graph have the same color.

### What is M coloring of a graph?

M-coloring of a graph is the process of assigning M colors to the vertices of a given graph, such that no two adjacent vertices share the same color. If an edge in the graph joins two vertices, then they must have different colors allotted to them.

### What is the concept of map coloring?

Map coloring is assigning colors to map regions so that no adjacent regions share the same color. It's used for visual clarity in cartography and has various real-world applications.

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

Here are some recommended problems to test your understanding of graphs