Problem Statement
We are given a graph, we need to assign colors to the vertices of the graph. In the graph coloring problem, we have a graph and m colors, we need to find a way to color the vertices of the graph using the m colors such that any two adjacent vertices are not having the same color.
Refer to the example and explanation sections for more details and the approach section to understand the solution to the graph coloring problem.
Note: The graph coloring problem is also known as the vertex coloring problem.
Example
The given (input) graph is :
The user needs to color the graph using m colors i.e. in this problem, m is given as 2.
After the graph coloring problem is solved, the colored graph will look like this:
Example Explanation
Before moving into the explanation of the graph coloring problem, let us first understand the term Chromatic Number. The chromatic number is the minimum number of colors needed to color the graph with the constraint that no two adjacent vertices have the same color.
For the explanation of the example, let us first number the vertices.
We have the graph with 4 vertices and the value of m is 2.
Let us suppose that we have started with color-1 (i.e. orange color) and we colored the first vertex with the color-1. Now the connected vertex (vertex-2) must be colored with different colors, so we colored the second vertex with the color-2 (blue).
The current situation after the vertex-1 and vertex-2 are colored is:
For the third vertex, we can use another color but the graph coloring problem states that we have to use the minimum number of colors. So. we can color the vertex-3 with the color-1 (orange).
Finally for the last vertex, i.e. vertex-4 we cannot use the color-1, so we colored it with the color-2 (blue).
Hence, all the vertices of the graph coloring problem are colored with only 2 colors (m = 2).
Constraints
- The first input is the number of vertices present in the graph i.e. n (1 ≤ n ≤ $10^3$).
- The second input is the sequential set of vertices of the graph.
- The third input is the value of m $(1 <= m <= n)$ i.e. number of colors to be used for the graph coloring problem.
In some problems, you may find the number of test cases represented by t. So, we only need to call the graph coloring problem function t-times.
Approach 1: Brute Force
The brute force approach to solving the graph coloring problem can be generating all the possible color combinations. After the color generation, we can check if any two adjacent vertices are having the same color or not. The time complexity will be huge as we have to generate all the possible combinations.
Note: All the possible combinations can be $m ^ V$ where V is the number of vertices.
Pseudo code can be:
- Define a recursive function that takes the current index (i), several vertices, and the color array for output.
- Check if the current color is safe i.e. no two adjacent vertices have the same color. Then print the current color configuration and break the loop.
- Assign a color to the vertex. The range of assigned colors is from 1 to m.
- Now, for every color assigned, call the recursive function.
- If the recursive call returns true then the coloring is possible. So, break the loop and return true.
C++ Code:
#include <bits/stdc++.h>
using namespace std;
/*
defining a macro that denotes the total number of vertices of the graph
*/
#define V 4
/* A function to print the color configuration*/
void printConfiguration(int colorArray[]) {
cout << "The assigned colors are as follows: " << endl;
for (int i = 0; i < V; i++)
cout << "Vertex: " << i << " Color: " << colorArray[i] << endl;
}
/*
A function that will check if the current color of the graph is safe or not.
*/
bool isSafe(bool graph[V][V], int colorArray[]) {
for (int i = 0; i < V; i++)
for (int j = i + 1; j < V; j++)
if (graph[i][j] && colorArray[j] == colorArray[i])
return false;
return true;
}
/*
A recursive function that takes the current index, number of vertices, and the color array. If the recursive call returns true then the coloring is possible. It returns
false if the m colors cannot be assigned.
*/
bool graphColoringAlgorithm(bool graph[V][V], int m, int i,
int colorArray[V]) {
/*
If we have reached the last vertex then check and print the configuration.
*/
if (i == V) {
if (isSafe(graph, colorArray)) {
printConfiguration(colorArray);
return true;
}
return false;
}
// Assigning color to the vertex and recursively calling the function.
for (int j = 1; j <= m; j++) {
colorArray[i] = j;
if (graphColoringAlgorithm(graph, m, i + 1, colorArray))
return true;
colorArray[i] = 0;
}
return false;
}
int main() {
bool graph[V][V] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0},
};
int m = 3;
int colorArray[V];
/*
Initially, the color array is initialized with 0.
*/
for (int i = 0; i < V; i++)
colorArray[i] = 0;
if (graphColoringAlgorithm(graph, m, 0, colorArray))
cout << "Coloring is possible!";
else
cout << "Coloring is not possible!";
return 0;
}Java Code:
public class GraphColoring {
/*
V denotes the total number of vertices of the graph
*/
static int V = 4;
/* A function to print the color configuration*/
static void printConfiguration(int colorArray[]) {
System.out.println("The assigned colors are as follows: ");
for (int i = 0; i < V; i++)
System.out.println("Vertex: " + i + " Color: " + colorArray[i]);
}
/*
A function that will check if the current color of the graph is safe or not.
*/
static boolean isSafe(boolean graph[][], int colorArray[]) {
for (int i = 0; i < V; i++)
for (int j = i + 1; j < V; j++)
if (graph[i][j] && colorArray[j] == colorArray[i])
return false;
return true;
}
/*
A recursive function that takes the current index, number of vertices, and the color array. If the recursive call returns true then the coloring is possible. It returns false if the m colors cannot be assigned.
*/
static boolean graphColoringAlgorithm(boolean graph[][], int m, int i,
int colorArray[]) {
/*
If we have reached the last vertex then check and print the configuration.
*/
if (i == V) {
if (isSafe(graph, colorArray)) {
printConfiguration(colorArray);
return true;
}
return false;
}
// Assigning color to the vertex and recursively calling the function.
for (int j = 1; j <= m; j++) {
colorArray[i] = j;
if (graphColoringAlgorithm(graph, m, i + 1, colorArray))
return true;
colorArray[i] = 0;
}
return false;
}
// Driver code
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;
int[] colorArray = new int[V];
/*
Initially, the color array is initialized with 0.
*/
for (int i = 0; i < V; i++)
colorArray[i] = 0;
if (graphColoringAlgorithm(graph, m, 0, colorArray))
System.out.println("Coloring is possible!");
else
System.out.println("Coloring is not possible!");
}
}Python Code:
# A function to print the color configuration.
def printConfiguration(colorArray):
print("The assigned colors are as follows:")
for i in range(4):
print("Vertex: ",
i, " Color: ", colorArray[i])
"""
A function that will check if the current colorArray of the graph is safe or not.
"""
def isSafe(graph, colorArray):
for i in range(4):
for j in range(i + 1, 4):
if (graph[i][j] and colorArray[j] == colorArray[i]):
return False
return True
"""
A recursive function that takes the current index, number of vertices, and the color array. If the recursive call returns true then the coloring is possible. It returns
false if the m colors cannot be assigned.
"""
def graphColoringAlgorithm(graph, m, i, colorArray):
# If we have reached the last vertex then check and print the configuration.
if (i == 4):
if (isSafe(graph, colorArray)):
printConfiguration(colorArray)
return True
return False
# Assigning color to the vertex and recursively calling the function.
for j in range(1, m + 1):
colorArray[i] = j
if (graphColoringAlgorithm(graph, m, i + 1, colorArray)):
return True
colorArray[i] = 0
return False
if __name__ == '__main__':
graph = [
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0],
]
m = 3
# Initially the color list is initialized with 0.
colorArray = [0 for i in range(4)]
if (graphColoringAlgorithm(graph, m, 0, colorArray)):
print("Coloring is possible!")
else:
print("Coloring is not possible!")Output:
The assigned colors are as follows:
Vertex: 0 Color: 1
Vertex: 1 Color: 2
Vertex: 2 Color: 3
Vertex: 3 Color: 2
Coloring is possible!Complexity Analysis
In the brute force approach to the graph coloring problem, we are generating total $m^V$ combinations of the color. So, it requires exponential time.
Time Complexity
In the brute force approach to the graph coloring problem, the time complexity is $O(m^V)$.
Space Complexity
In the brute force approach to the graph coloring problem, we are not using any extra space but we are using the recursive stack for the recursive function call. So, the space complexity is O(V).
Approach 2: Backtracking
The backtracking approach to solving the graph coloring problem can be to assign the colors one after the other to the various vertices. The coloring will start with the first index only but before assigning any color, we would first check if it satisfies the constraint or not (i.e. no two adjacent vertices have the same color). If the current color assignment does not violate the condition then add it into the solution else, backtrack by returning false.
Pseudo code can be:
- Define a recursive function that takes the current index (i), several vertices, and the color array for output.
- Check if the current color is safe i.e. no two adjacent vertices have the same color. Then print the current color configuration and break the loop.
- Assign a color to the vertex. The range of assigned colors is from 1 to m.
- Now, for every color assigned, call the recursive function.
- If the recursive call returns true then the coloring is possible. So, break the loop and return true. Else, backtrack.
C++ Code:
#include <bits/stdc++.h>
using namespace std;
/*
defining a macro that denotes the total number of vertices of the graph
*/
#define V 4
/* A function to print the color configuration*/
void printConfiguration(int colorArray[]) {
cout << "The assigned colors are as follows: " << endl;
for (int i = 0; i < V; i++)
cout << "Vertex: " << i << " Color: " << colorArray[i] << endl;
}
/*
A function that will check if the current color of the graph is safe or not.
*/
bool isSafe(int v, bool graph[V][V],
int colorArray[], int vertex) {
for (int i = 0; i < V; i++)
if (graph[v][i] && vertex == colorArray[i])
return false;
return true;
}
/*
A recursive function that takes the current index, number of vertices, and the color array. If the recursive call returns true then the coloring is possible. It returns
false if the m colors cannot be assigned.
*/
bool graphColoringAlgorithmUtil(bool graph[V][V], int m,
int colorArray[], int currentVertex) {
// base case.
if (currentVertex == V)
return true;
for (int c = 1; c <= m; c++) {
if (isSafe(currentVertex, graph, colorArray, c)) {
colorArray[currentVertex] = c;
if (graphColoringAlgorithmUtil(
graph, m, colorArray, currentVertex + 1))
return true;
// backtracking
colorArray[currentVertex] = 0;
}
}
return false;
}
bool graphColoringAlgorithm(bool graph[V][V], int m) {
/*
Initially, the color array is initialized with 0.
*/
int colorArray[V];
for (int i = 0; i < V; i++)
colorArray[i] = 0;
// Call graphColoringAlgorithmUtil() for vertex 0
if (!graphColoringAlgorithmUtil(graph, m, colorArray, 0)) {
cout << "Coloring is not possible!";
return false;
}
cout << "Coloring is possible!";
printConfiguration(colorArray);
return true;
}
int main() {
bool graph[V][V] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0},
};
int m = 3;
graphColoringAlgorithm(graph, m);
return 0;
}Java Code:
public class GraphColoring {
/*
V denotes the total number of vertices of the graph
*/
static int V = 4;
// defining a color array that stores the result.
int colorArray[];
/* A function to print the color configuration*/
void printConfiguration(int colorArray[]) {
System.out.println("The assigned colors are as follows: ");
for (int i = 0; i < V; i++)
System.out.println("Vertex: " + i + " Color: " + colorArray[i]);
}
/*
A function that will check if the current color of the graph is safe or not.
*/
boolean isSafe(
int v, int graph[][], int colorArray[],
int vertex) {
for (int i = 0; i < V; i++)
if (graph[v][i] == 1 && vertex == colorArray[i])
return false;
return true;
}
/*
A recursive function that takes the current index, number of vertices, and the color array. If the recursive call returns true then the coloring is possible. It returns
false if the m colors cannot be assigned.
*/
boolean graphColoringAlgorithmUtil(
int graph[][], int m,
int colorArray[], int currentVertex) {
// base case
if (currentVertex == V)
return true;
for (int i = 1; i <= m; i++) {
if (isSafe(currentVertex, graph, colorArray, i)) {
colorArray[currentVertex] = i;
if (graphColoringAlgorithmUtil(
graph, m,
colorArray, currentVertex + 1))
return true;
// backtracking
colorArray[currentVertex] = 0;
}
}
return false;
}
boolean graphColoringAlgorithm(int graph[][], int m) {
/*
Initially, the color array is initialized with 0.
*/
colorArray = new int[V];
for (int i = 0; i < V; i++)
colorArray[i] = 0;
// Call graphColoringAlgorithmUtil() for vertex 0
if (!graphColoringAlgorithmUtil(
graph, m, colorArray, 0)) {
System.out.println(
"Coloring is not possible!");
return false;
}
System.out.println("Coloring is possible!");
printConfiguration(colorArray);
return true;
}
public static void main(String args[]) {
GraphColoring c = new GraphColoring();
int graph[][] = {
{ 0, 1, 1, 1 },
{ 1, 0, 1, 0 },
{ 1, 1, 0, 1 },
{ 1, 0, 1, 0 },
};
int m = 3;
c.graphColoringAlgorithm(graph, m);
}
}Python Code:
V = 4
# A function to print the color configuration.
def printConfiguration(colorArray):
print("The assigned colors are as follows:")
for i in range(4):
print("Vertex: ",
i, " Color: ", colorArray[i])
"""
A function that will check if the current colorArray of the graph is safe or not.
"""
def isSafe(v, colorArray, vertex):
for i in range(V):
if graph[v][i] == 1 and colorArray[i] == vertex:
return False
return True
"""
A recursive function that takes the current index, number of vertices, and the color array. If the recursive call returns true then the coloring is possible. It returns
false if the m colors cannot be assigned.
"""
def graphColoringAlgorithmUtil(m, colorArray, currentVertex):
# base case.
if currentVertex == V:
return True
for i in range(1, m + 1):
if isSafe(currentVertex, colorArray, i) == True:
colorArray[currentVertex] = i
if graphColoringAlgorithmUtil(m, colorArray, currentVertex + 1):
return True
# backtrack
colorArray[currentVertex] = 0
def graphColoringAlgorithm(colorArray, m):
# Initially the color array is initialized with 0.
colorArray = [0] * V
# Call graphColoringAlgorithmUtil() for vertex 0.
if graphColoringAlgorithmUtil(m, colorArray, 0) == None:
print("Coloring is not possible!")
return False
# Print the solution
print("Coloring is possible!")
printConfiguration(colorArray)
return True
if __name__ == '__main__':
graph = [
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0],
]
m = 3
graphColoringAlgorithm(graph, m)Output:
Coloring is possible!
The assigned colors are as follows:
Vertex: 0 Color: 1
Vertex: 1 Color: 2
Vertex: 2 Color: 2
Vertex: 3 Color: 2Complexity Analysis
In the backtracking approach of the graph coloring problem, we are generating total $m^V$ combinations of the color. So, it also requires exponential time.
Time Complexity
In the backtracking approach of the graph coloring problem, the time complexity is $O(m^V)$. In the backtracking approach, the average time complexity is less than $O(m^V)$.
Space Complexity
In the backtracking approach to the graph coloring problem, we are not using any extra space but we are using the recursive stack for the recursive function call. So, the space complexity is O(V).
Note: The backtracking approach and the brute force approach have the same time complexity as in the backtracking algorithm we are just eliminating the bad decisions while coloring the vertices.
Approach 3: Brooks’ Theorem
We can also solve this problem using Brook’s Theorem. Brook's theorem tells us about the relationship between the maximum degree of a graph and the chromatic number of the graph.
The statement of Brook's Theorem is:
For a simple connected graph G, which is neither is complete graph nor an odd cycled graph, the relationship between the maximum degree of a graph and the chromatic number of the graph is
X(G) ≤ k, where k denotes the maximum degree of the graph G, and X(G) denotes the chromatic number of the same graph G.
Approach 4: Greedy Approach
The greedy approach to solving the graph coloring problem can be using at most x+1 colors if the maximum degree of a vertex is x. The greedy approach does not guarantee that the minimum number of colors are used but, surely, the maximum x+1 colors are used where x is the maximum degree of any vertex in the given graph.
We will color the current vertex with the least-numbered color. After that, we will check if the currently assigned least color has been used previously for any adjacent vertex of the current vertex or not. If it is not used then we can continue the process to the next vertex else, we will assign the next color.
Let us see the pseudo-code for the same.
Pseudo code can be:
- Color the first vertex of the graph with the first color.
- Repeat the below step for the remaining vertices.
Color the current vertex with the minimum numbered color. Make sure that the selected minimum number color has not been used previously for any adjacent vertex of the current vertex.
C++ Code:
#include <bits/stdc++.h>
using namespace std;
// A class representing the graph
class Graph {
int V;
list<int> *graph;
public:
// Constructor
Graph(int V) {
this->V = V;
graph = new list<int>[V];
}
// a function that will add an edge to the graph.
void insertEdge(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
// Greedy algo of printing the colors
void graphColoringAlgorithm() {
int colorArray[V];
// Assign 0 as the first vertex
colorArray[0] = 0;
/*
Assigning -1 to the rest of the vertex means the rest of the colors are not ye assigned
*/
for (int i = 1; i < V; i++)
colorArray[i] = -1;
// A temporary array to store the available colors.
bool temp[V];
for (int i = 0; i < V; i++)
temp[i] = false;
// Assign colors to the rest of the vertices.
for (int u = 1; u < V; u++) {
// an iterator to iterate over graph list.
list<int>::iterator i;
for (i = graph[u].begin(); i != graph[u].end(); i++)
if (colorArray[*i] != -1)
temp[colorArray[*i]] = true;
int j;
for (j = 0; j < V; j++)
if (temp[j] == false)
break;
colorArray[u] = j;
for (i = graph[u].begin(); i != graph[u].end(); ++i)
if (colorArray[*i] != -1)
temp[colorArray[*i]] = false;
}
// printing the assigned colors.
for (int i = 0; i < V; i++)
cout << "Vertex: " << i << " Color: " << colorArray[i] << endl;
}
};
int main() {
Graph g(5);
g.insertEdge(0, 1);
g.insertEdge(0, 2);
g.insertEdge(1, 2);
g.insertEdge(1, 3);
g.insertEdge(2, 3);
g.insertEdge(3, 4);
cout << "The assigned colors of the graph is:" << endl;
g.graphColoringAlgorithm();
return 0;
}
Java Code:
import java.util.*;
import java.util.LinkedList;
// A class representing the graph
class Graph {
private int V;
private LinkedList<Integer> graph[];
// Constructor
Graph(int v) {
V = v;
graph = new LinkedList[v];
for (int i = 0; i < v; ++i)
graph[i] = new LinkedList();
}
// a function that will add an edge in the graph.
void insertEdge(int u, int v) {
graph[u].add(v);
graph[v].add(u);
}
// Greedy algo of printing the colors
void graphColoringAlgorithm() {
int colorArray[] = new int[V];
/*
Assigning -1 to the rest of the vertex means the rest of the colors are not ye assigned
*/
Arrays.fill(colorArray, -1);
// Assign 0 as the first vertex
colorArray[0] = 0;
// A temporary array to store the temp colors.
boolean temp[] = new boolean[V];
Arrays.fill(temp, true);
// Assign colors to the rest of the vertices.
for (int u = 1; u < V; u++) {
// an iterator to iterate over graph list.
Iterator<Integer> it = graph[u].iterator();
while (it.hasNext()) {
int i = it.next();
if (colorArray[i] != -1)
temp[colorArray[i]] = false;
}
int j;
for (j = 0; j < V; j++) {
if (temp[j])
break;
}
colorArray[u] = j;
Arrays.fill(temp, true);
}
// printing the assigned colors.
for (int i = 0; i < V; i++)
System.out.println("Vertex: " + i + " Color: " + colorArray[i]);
}
public static void main(String args[]) {
Graph g = new Graph(5);
g.insertEdge(0, 1);
g.insertEdge(0, 2);
g.insertEdge(1, 2);
g.insertEdge(1, 3);
g.insertEdge(2, 3);
g.insertEdge(3, 4);
System.out.println("The assigned colors of the graph is:");
g.graphColoringAlgorithm();
}
}
Python Code:
# a function that will add an edge to the graph.
def insertEdge(graph, u, v):
graph[u].append(v)
graph[v].append(u)
return graph
# Greedy algo of printing the colors
def greedyColoring(graph, V):
"""
Assigning False to the rest of the vertex means the rest of the colors are not ye assigned
"""
colorArray = [-1] * V
# Assign 0 as the first vertex
colorArray[0] = 0
"""
A temporary array to store the available colors.
"""
temp = [False] * V
# Assign colors to the rest of the vertices.
for u in range(1, V):
for i in graph[u]:
if (colorArray[i] != -1):
temp[colorArray[i]] = True
j = 0
while j < V:
if (temp[j] == False):
break
j += 1
colorArray[u] = j
# reset the values for next iteration.
for i in graph[u]:
if (colorArray[i] != -1):
temp[colorArray[i]] = False
# printing the assigned colors.
for i in range(u):
print("Vertex: ",
i, " Color: ", colorArray[i])
if __name__ == '__main__':
g = [[] for i in range(5)]
g = insertEdge(g, 0, 1)
g = insertEdge(g, 0, 2)
g = insertEdge(g, 1, 2)
g = insertEdge(g, 1, 3)
g = insertEdge(g, 2, 3)
g = insertEdge(g, 3, 4)
print("The assigned colors of the graph is:")
greedyColoring(g, 5)
Output:
The assigned colors of the graph is:
Vertex: 0 Color: 0
Vertex: 1 Color: 1
Vertex: 2 Color: 2
Vertex: 3 Color: 0
Vertex: 4 Color: 1
Complexity Analysis
In the greedy approach to the graph coloring problem, we are greedily assigning a color to each vertex of the graph as well as checking if the assigned color meets the criteria or not (no two adjacent vertexes have the same color).
Time Complexity:
In the greedy approach to the graph coloring problem, the time complexity is O(V2+E) in the worst case.
Space Complexity
In the greedy approach to the graph coloring problem, we are not using any extra space. So, the space complexity is O(1).
Conclusion
- The brute force approach to solving the graph coloring problem can be generating all the possible color combinations and checking if any two adjacent vertices are having the same color or not.
- The backtracking approach is also a type of brute force. It is just used to eliminate bad decisions while coloring the vertices.
- In the brute force approach to the graph coloring problem, the time complexity is O(mV), and space complexity is O(V).
- The backtracking approach to solving the graph coloring problem can be to assign the colors one after the other to the various vertices. If the current color assignment does not violate the condition then add it into the solution else, backtrack by returning false.
- In the backtracking approach to the graph coloring problem, the time complexity is O(mV), and space complexity is O(V).
- The greedy approach to solving the graph coloring problem can be used at most x+1 colors if the maximum degree of a vertex is x. The idea is to color the current vertex with the minimum numbered color that has not been used previously for any adjacent vertex of the current vertex.
- In the greedy approach to the graph coloring problem, the time complexity is O(V2+E) in the worst case, and space complexity is O(1).
- We can also solve this problem using Brook’s Theorem. Brook’s theorem tells us about the relationship between the maximum degree of a graph and the chromatic number of the graph.
