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

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
• 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 = *(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 ## Edit Distance Problem

##### Next Post 