Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# M Coloring Problem

Last Updated on November 18, 2022 by Sumit Kumar

Given an undirected graph and `M` colors, the problem is to find if it is possible to color the graph with at most `M` colors or not.

See original problem statement here

## How to Solve M Coloring Problem :

Idea is to assign different colors `(1-M)` to all the adjacent vertices. If at any point the color of any two adjacent vertices are same then we say it is not possible, otherwise it is.

## How backtracking Help:

We will use backtracking to solve the above problem.

Backtracking is the approach to solve the problem by testing all possible combinations. If any subproblem does not fit the given constraint then we discard the complete subproblem (backtrack), moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.

We will take a color array `color[]` to store `M` colours. Now iterate through `color[]` , then we will assign each colour to all vertices one-by-one. If any colour assignment does not match the constraints then we will backtrack and unassign the colour which has been assigned to the vertex earlier. If the vertex count reaches the total number of vertices we will return true, and if none of the assignment matches the given condition (adjacent vertices must have different colours) then we will return false.

## Algorithm to Solve M Coloring Problem:

colour():

1. If `index == number.of.vertices`, return TRUE.
2. else, for every `k= 1` to `M` :
• assign color to the current vertex, `v`, (`color[v]=k`)
• if colour(graph,vertex+1,color)==TRUE, return true
• else ,
• mark the colour as unassigned, (`colour[v]=0`) (backtracking step).
• If none of the combination satisfies, return FALSE.

### Complexity Analysis :

In this method each vertex has `M` different choices of colors. So the total time complexity is MV , where `M` is the number of colours and `V` is the number of vertices.

## Program to Solve M Coloring Problem:

``` #include <stdio.h>
int V;

int isSafe(int v, int graph[V][V],int color[], int c)
{
for (int i = 0; i < V; i++)
if (
graph[v][i] && c == color[i])
return 0;
return 1;
}

int colour(int graph[V][V], int m,int color[], int v)
{

if (v == V)
return 1;

for (int c = 1; c <= m; c++)
{
if (isSafe(
v, graph, color, c)) {
color[v] = c;

if ( colour(graph, m, color, v + 1)== 1)
return 1;

color[v] = 0;
}
}

return 0;
}

int graphColoring(int graph[V][V], int m)
{

int color[V];
for (int i = 0; i < V; i++)
color[i] = 0;

if (
colour(graph, m, color, 0)== 0) {
return 0;
}

return 1;
}

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int e;
scanf("%d %d",&V,&e);
int graph[V][V];
for(int i=0;i<V;i++)
{
for(int j=0;j<V;j++)
graph[i][j]=0;
}
while(e--)
{
int u,v;
scanf("%d %d",&u,&v);
graph[u][v]=1;
graph[v][u]=1;
}
int m; // Number of colors
scanf("%d",&m);
printf("%d\n",graphColoring(graph, m));
}
return 0;
}
```
```#include<iostream>
#define V 100

using namespace std;

int isSafe(int v, int graph[V][V],int color[], int c)
{
for (int i = 0; i < V; i++)
if (
graph[v][i] && c == color[i])
return 0;
return 1;
}

int colour(int graph[V][V], int m,int color[], int v)
{

if (v == V)
return 1;

for (int c = 1; c <= m; c++)
{
if (isSafe(
v, graph, color, c)) {
color[v] = c;

if ( colour(graph, m, color, v + 1)== 1)
return 1;

color[v] = 0;
}
}

return 0;
}

int graphColoring(int graph[V][V], int m)
{

int color[V];
for (int i = 0; i < V; i++)
color[i] = 0;

if (
colour(graph, m, color, 0)== 0) {
return 0;
}

return 1;
}

int main()
{
int t;
cin>>t;
while(t--)
{
int n,e;
cin>>n>>e;
int graph[V][V];
for(int i=0;i<V;i++)
{
for(int j=0;j<V;j++)
graph[i][j]=0;
}
while(e--)
{
int u,v;
cin>>u>>v;
graph[u][v]=1;
graph[v][u]=1;
}
int m; // Number of colors
cin>>m;
cout<<graphColoring(graph, m)<<endl;
}
return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main{
final int V = 100;
int color[];

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;
}

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)) {

return false;
}

return true;
}

public static void main(String args[])
{
Main m = new Main();
Scanner sc= new Scanner(System.in);
int t = sc.nextInt();
while(t-->0)
{
int n = sc.nextInt();
int e = sc.nextInt();
int [][]graph = new int [m.V][m.V];
for(int i=0;i<m.V;i++)
{
for(int j = 0; j<m.V;j++)
{
graph[i][j]=0;
}
}

while(e-->0)
{
int u = sc.nextInt();
int v = sc.nextInt();
graph[u][v]=1;
graph[v][u]=1;
}
int no = sc.nextInt();
if(m.graphColoring(graph, no)==false)
System.out.println("0");
else
System.out.println("1");
}
}
}
```
```V = 100
def isSafe(v, graph, color, c):

V = 100
for i in range(V):

if (graph[v][i] and c == color[i]):
return 0

return 1

def colour( graph, m, color, v):

if (v == V):
return 1

for c in range(1, m + 1):

if (isSafe(v, graph, color, c)):
color[v] = c

if ( colour(graph, m, color, v + 1)== 1):
return 1

color[v] = 0

return 0

def graphColoring( graph, m):

V = 100
color = [0] * V

for i in range(V):
color[i] = 0

if (colour(graph, m, color, 0)== 0):
return 0

return 1

for _ in range(int(input())):
n, e = map(int,input().split())
graph = [[0 for i in range(100)] for j in range(100)]
while e:
e -= 1
u, v = map(int,input().split())
graph[u][v] = 1
graph[v][u] = 1
m = int(input())
print(graphColoring(graph, m))

```

[forminator_quiz id="2077"]

This article tried to discuss the concept of Backtracking. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming