Scribd
Upload
46 views

M-Coloring Problem

The M-Coloring problem involves assigning m different colors to the nodes of a graph such that no two adjacent vertices share the same color. The backtracking algorithm is used to find a valid color assignment, and if successful, it displays the color assigned to each vertex. An example implementation in C demonstrates how to solve the problem using a graph represented by an adjacency matrix.

Uploaded by

chanduramcharanroyal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
46 views

M-Coloring Problem

The M-Coloring problem involves assigning m different colors to the nodes of a graph such that no two adjacent vertices share the same color. The backtracking algorithm is used to find a valid color assignment, and if successful, it displays the color assigned to each vertex. An example implementation in C demonstrates how to solve the problem using a graph represented by an adjacency matrix.

Uploaded by

chanduramcharanroyal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Page 1 of 4

M-Coloring Problem
What is M-Coloring Problem?
In the M-Coloring problem, our task is to find if it is possible to assign nodes of a given graph with m
different colors, such that no two adjacent vertices of the graph are of the same colors. If a solution
exists, then display which color is assigned to each vertex. The m-coloring problem is practically used
to solve problems like clustering, scheduling, job allocation problems and many more.

A graph is an abstract data type (ADT) consisting of a set of objects that are connected via
links.

Input Output Scenario


Suppose the given undirected graph G(V, E) and its adjacency matrix are as follows −

Let the maximum color m = 3, which indicates the maximum number of colors that can be used. The
backtracking algorithm can be used to solve the m-coloring problem for the above graph. This algorithm
will return which node will be assigned with which color. If the solution is not possible, it will return
false.

For this case, the output should be Node 0 -> color 1, Node 1 -> color 2, Node 2 -> color 3, Node 3 ->
color 2. The figure below illustrates the same −
Page 2 of 4

Solving M-Coloring Problem using Backtracking Approach


The naive way to solve m-coloring problem is by generating all possible combinations of vertices with
colors and checking if any combination satisfies the given constraints. However, this approach is
inefficient for larger graphs.

To solve m-coloring problem using the backtracking approach, follow the below steps −

Starting from vertex 0, we will try to assign colors one by one to different nodes.

However, before assigning, we have to check whether the color is safe or not. Color is not safe
when adjacent vertices contain the same color.

Next, we will check if is there any color assignment that satisfies the constraint. If it does, we
mark that assignment as a solution to the m-coloring problem.

Example
In the following example, we will illustrate how to solve the m-coloring problem in a given undirected
graph.

C C++ Java Python

Open Compiler

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define V 4
bool graph[V][V] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
Page 3 of 4

{1, 0, 1, 0}
};
void showColors(int color[]) {
printf("Assigned Colors are:\n");
for (int i = 0; i < V; i++)
printf("%d ", color[i]);
printf("\n");
}
//check whether putting a color valid for v
bool isValid(int v, int color[], int c) {
for (int i = 0; i < V; i++)
if (graph[v][i] && c == color[i])
return false;
return true;
}
bool graphColoring(int colors, int color[], int vertex) {
//when all vertices are considered
if (vertex == V)
return true;
for (int col = 1; col <= colors; col++) {
//check whether color is valid or not
if (isValid(vertex, color, col)) {
color[vertex] = col;
// go for additional vertices
if (graphColoring(colors, color, vertex + 1))
return true;
color[vertex] = 0;
}
}
//when no colors can be assigned
return false;
}
bool checkSolution(int m) {
//make color matrix for each vertex
int *color = (int *)malloc(V * sizeof(int));
for (int i = 0; i < V; i++)
//initially set to 0
color[i] = 0;
//for vertex 0 check graph coloring
if (graphColoring(m, color, 0) == false) {
printf("Solution does not exist.\n");
free(color);
Page 4 of 4

return false;
}
showColors(color);
free(color);
return true;
}

int main() {
// Number of colors
int colors = 3;
checkSolution(colors);
return 0;
}

Output

Assigned Colors are:


1232

You might also like