Problem Statement
Given an undirected graph G(V, E), where V is the set of vertices and E is the set of edges, the Graph Coloring Problem is to find the minimum number of colors required to color the vertices of the graph in such a way that no two adjacent vertices have the same color.
In other words, you want to assign colors to each vertex in the graph so that no two adjacent vertices share the same color. The objective is to minimize the total number of colors used.
Approach 1 – Brute Force
Brute force is a straightforward but often impractical approach for solving the Graph Coloring Problem. It involves systematically trying all possible color assignments until a valid coloring is found. Here’s how you can implement a brute force approach for the Graph Coloring Problem
Algorithm
- Initialize a list of colors, such as {1, 2, 3, …}, to represent the available colors.
- Start with the first vertex in the graph.
- Assign the first color to the current vertex.
- Move on to the next vertex and repeat the process
- Check each available color.
- For each color, check if it’s valid (i.e., no adjacent vertex has the same color).
- If a valid color is found, assign it to the current vertex and proceed to the next vertex.
- If no valid color is found for the current vertex, backtrack to the previous vertex and try the next available color.
5.Repeat step 4 until all vertices are colored or until no valid coloring is possible.
6.If a valid coloring is found (all vertices are colored without conflicts), the algorithm terminates, and you have a solution.
C++ Implementation
#include <iostream>
#include <vector>
using namespace std;
const int MAX_VERTICES = 100; // Adjust the maximum number of vertices as needed
vector<int> graph[MAX_VERTICES];
int colorAssignment[MAX_VERTICES];
int numVertices, numColors;
bool isSafe(int v, int c) {
for (int neighbor : graph[v]) {
if (colorAssignment[neighbor] == c) {
return false;
}
}
return true;
}
bool graphColoringUtil(int v) {
if (v == numVertices) {
return true; // All vertices are colored
}
for (int color = 1; color <= numColors; color++) {
if (isSafe(v, color)) {
colorAssignment[v] = color;
if (graphColoringUtil(v + 1)) {
return true; // Recursively color the next vertex
}
colorAssignment[v] = 0; // Backtrack if no valid coloring is found
}
}
return false; // No valid coloring exists
}
bool solveGraphColoring(int vertices, int edges, int colors, vector<pair<int, int>> edgesList) {
numVertices = vertices;
numColors = colors;
for (int i = 0; i < MAX_VERTICES; i++) {
graph[i].clear();
colorAssignment[i] = 0;
}
for (pair<int, int> edge : edgesList) {
graph[edge.first].push_back(edge.second);
graph[edge.second].push_back(edge.first);
}
if (graphColoringUtil(0)) {
cout << “Valid Coloring: “;
for (int i = 0; i < numVertices; i++) {
cout << colorAssignment[i] << ” “;
}
cout << endl;
return true;
} else {
cout << “No valid coloring exists.” << endl;
return false;
}
}
int main() {
int vertices = 4;
int edges = 4;
int colors = 3;
vector<pair<int, int>> edgesList = {{0, 1}, {1, 2}, {2, 3}, {3, 0}};
if (solveGraphColoring(vertices, edges, colors, edgesList)) {
cout << “Graph is colored.” << endl;
} else {
cout << “Graph cannot be colored.” << endl;
}
return 0;
}
Java Implementation
import java.util.ArrayList;
import java.util.List;
public class GraphColoring {
private static final int MAX_VERTICES = 100; // Adjust the maximum number of vertices as needed
private static List<Integer>[] graph = new ArrayList[MAX_VERTICES];
private static int[] colorAssignment = new int[MAX_VERTICES];
private static int numVertices, numColors;
private static boolean isSafe(int v, int c) {
for (int neighbor : graph[v]) {
if (colorAssignment[neighbor] == c) {
return false;
}
}
return true;
}
private static boolean graphColoringUtil(int v) {
if (v == numVertices) {
return true; // All vertices are colored
}
for (int color = 1; color <= numColors; color++) {
if (isSafe(v, color)) {
colorAssignment[v] = color;
if (graphColoringUtil(v + 1)) {
return true; // Recursively color the next vertex
}
colorAssignment[v] = 0; // Backtrack if no valid coloring is found
}
}
return false; // No valid coloring exists
}
private static boolean solveGraphColoring(int vertices, int edges, int colors, int[][] edgesList) {
numVertices = vertices;
numColors = colors;
for (int i = 0; i < MAX_VERTICES; i++) {
graph[i] = new ArrayList<>();
colorAssignment[i] = 0;
}
for (int[] edge : edgesList) {
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
if (graphColoringUtil(0)) {
System.out.print(“Valid Coloring: “);
for (int i = 0; i < numVertices; i++) {
System.out.print(colorAssignment[i] + ” “);
}
System.out.println();
return true;
} else {
System.out.println(“No valid coloring exists.”);
return false;
}
}
public static void main(String[] args) {
int vertices = 4;
int edges = 4;
int colors = 3;
int[][] edgesList = {{0, 1}, {1, 2}, {2, 3}, {3, 0}};
if (solveGraphColoring(vertices, edges, colors, edgesList)) {
System.out.println(“Graph is colored.”);
} else {
System.out.println(“Graph cannot be colored.”);
}
}
}
Python Implementation
MAX_VERTICES = 100 # Adjust the maximum number of vertices as needed
graph = [[] for _ in range(MAX_VERTICES)]
colorAssignment = [-1] * MAX_VERTICES
numVertices, numColors = 0, 0
def isSafe(v, c):
for neighbor in graph[v]:
if colorAssignment[neighbor] == c:
return False
return True
def graphColoringUtil(v):
global numVertices, numColors
if v == numVertices:
return True # All vertices are colored
for color in range(1, numColors + 1):
if isSafe(v, color):
colorAssignment[v] = color
if graphColoringUtil(v + 1):
return True # Recursively color the next vertex
colorAssignment[v] = -1 # Backtrack if no valid coloring is found
return False # No valid coloring exists
def solveGraphColoring(vertices, edges, colors, edgesList):
global numVertices, numColors
numVertices = vertices
numColors = colors
for i in range(MAX_VERTICES):
graph[i].clear()
colorAssignment[i] = -1
for edge in edgesList:
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
if graphColoringUtil(0):
print(“Valid Coloring:”, end=” “)
for i in range(numVertices):
print(colorAssignment[i], end=” “)
print()
return True
else:
print(“No valid coloring exists.”)
return False
vertices = 4
edges = 4
colors = 3
edgesList = [(0, 1), (1, 2), (2, 3), (3, 0)]
if solveGraphColoring(vertices, edges, colors, edgesList)
Approach 2- Backtracking
The backtracking algorithm is another approach for solving the Graph Coloring Problem. It works by recursively exploring different color assignments for each vertex while keeping track of the chosen colors and checking if a valid coloring is possible. If an invalid coloring is detected, it backtracks and tries a different color until a valid coloring or the absence of one is determined.
Algorithm
- Initialize an array to store the color assigned to each vertex.
- Start with the first vertex in the graph.
- For the current vertex, try assigning each available color one by one and recursively explore the next vertex.
- If a valid coloring is found for all vertices, the algorithm terminates, and you have a solution.
- If at any point a coloring is not valid (i.e., two adjacent vertices have the same color), backtrack to the previous vertex and try the next available color.
- Repeat steps 3-5 until all vertices are colored, or it is determined that no valid coloring exists.
C++ Implementation
#include <iostream>
#include <vector>
using namespace std;
const int MAX_VERTICES = 100; // Adjust the maximum number of vertices as needed
vector<int> graph[MAX_VERTICES];
int colorAssignment[MAX_VERTICES];
int numVertices, numColors;
bool isSafe(int v, int c) {
for (int neighbor : graph[v]) {
if (colorAssignment[neighbor] == c) {
return false;
}
}
return true;
}
bool graphColoringUtil(int v) {
if (v == numVertices) {
return true; // All vertices are colored
}
for (int color = 0; color < numColors; color++) {
if (isSafe(v, color)) {
colorAssignment[v] = color;
if (graphColoringUtil(v + 1)) {
return true; // Recursively color the next vertex
}
colorAssignment[v] = -1; // Backtrack if no valid coloring is found
}
}
return false; // No valid coloring exists
}
bool solveGraphColoring(int vertices, int edges, int colors, vector<pair<int, int>> edgesList) {
numVertices = vertices;
numColors = colors;
for (int i = 0; i < MAX_VERTICES; i++) {
graph[i].clear();
colorAssignment[i] = -1;
}
for (pair<int, int> edge : edgesList) {
graph[edge.first].push_back(edge.second);
graph[edge.second].push_back(edge.first);
}
if (graphColoringUtil(0)) {
cout << “Valid Coloring: “;
for (int i = 0; i < numVertices; i++) {
cout << colorAssignment[i] << ” “;
}
cout << endl;
return true;
} else {
cout << “No valid coloring exists.” << endl;
return false;
}
}
int main() {
int vertices = 4;
int edges = 4;
int colors = 3;
vector<pair<int, int>> edgesList = {{0, 1}, {1, 2}, {2, 3}, {3, 0}};
if (solveGraphColoring(vertices, edges, colors, edgesList)) {
cout << “Graph is colored.” << endl;
} else {
cout << “Graph cannot be colored.” << endl;
}
return 0;
}
Java Implementation
import java.util.ArrayList;
import java.util.List;
public class GraphColoring {
private static final int MAX_VERTICES = 100; // Adjust the maximum number of vertices as needed
private static List<Integer>[] graph = new ArrayList[MAX_VERTICES];
private static int[] colorAssignment = new int[MAX_VERTICES];
private static int numVertices, numColors;
private static boolean isSafe(int v, int c) {
for (int neighbor : graph[v]) {
if (colorAssignment[neighbor] == c) {
return false;
}
}
return true;
}
private static boolean graphColoringUtil(int v) {
if (v == numVertices) {
return true; // All vertices are colored
}
for (int color = 0; color < numColors; color++) {
if (isSafe(v, color)) {
colorAssignment[v] = color;
if (graphColoringUtil(v + 1)) {
return true; // Recursively color the next vertex
}
colorAssignment[v] = -1; // Backtrack if no valid coloring is found
}
}
return false; // No valid coloring exists
}
private static boolean solveGraphColoring(int vertices, int edges, int colors, int[][] edgesList) {
numVertices = vertices;
numColors = colors;
for (int i = 0; i < MAX_VERTICES; i++) {
graph[i] = new ArrayList<>();
colorAssignment[i] = -1;
}
for (int[] edge : edgesList) {
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
if (graphColoringUtil(0)) {
System.out.print(“Valid Coloring: “);
for (int i = 0; i < numVertices; i++) {
System.out.print(colorAssignment[i] + ” “);
}
System.out.println();
return true;
} else {
System.out.println(“No valid coloring exists.”);
return false;
}
}
public static void main(String[] args) {
int vertices = 4;
int edges = 4;
int colors = 3;
int[][] edgesList = {{0, 1}, {1, 2}, {2, 3}, {3, 0}};
if (solveGraphColoring(vertices, edges, colors, edgesList)) {
System.out.println(“Graph is colored.”);
} else {
System.out.println(“Graph cannot be colored.”);
}
}
}
Python Implementation
MAX_VERTICES = 100 # Adjust the maximum number of vertices as needed
graph = [[] for _ in range(MAX_VERTICES)]
colorAssignment = [-1] * MAX_VERTICES
numVertices, numColors = 0, 0
def isSafe(v, c):
for neighbor in graph[v]:
if colorAssignment[neighbor] == c:
return False
return True
def graphColoringUtil(v):
global numVertices, numColors
if v == numVertices:
return True # All vertices are colored
for color in range(numColors):
if isSafe(v, color):
colorAssignment[v] = color
if graphColoringUtil(v + 1):
return True # Recursively color the next vertex
colorAssignment[v] = -1 # Backtrack if no valid coloring is found
return False # No valid coloring exists
def solveGraphColoring(vertices, edges, colors, edgesList):
global numVertices, numColors
numVertices = vertices
numColors = colors
for i in range(MAX_VERTICES):
graph[i].clear()
colorAssignment[i] = -1
for edge in edgesList:
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
if graphColoringUtil(0):
print(“Valid Coloring:”, end=” “)
for i in range(numVertices):
print(colorAssignment[i], end=” “)
print()
return True
else:
print(“No valid coloring exists.”)
return False
vertices = 4
edges = 4
colors = 3
edgesList = [(0, 1), (1, 2), (2, 3), (3, 0)]
if solveGraphColoring(vertices, edges, colors, edgesList):
print(“Graph is colored.”)
else:
print(“Graph cannot be colored.”)
FAQ’S
1.What is the Graph Coloring Problem?
The Graph Coloring Problem is a classic combinatorial optimization problem in graph theory. It involves assigning colors to the vertices of an undirected graph in such a way that no two adjacent vertices share the same color.
2 .Why is the Graph Coloring Problem important?
Graph coloring has practical applications in various fields, including scheduling, register allocation in compilers, frequency assignment in wireless networks, and map coloring. It also serves as a fundamental problem in computer science and combinatorial optimization.
3.What are the main objectives of the Graph Coloring Problem?
The primary objectives are to minimize the number of colors used to color the graph’s vertices (minimization version) or to determine if a graph can be colored with a given number of colors (decision version).
4.Is the Graph Coloring Problem easy to solve?
No, the Graph Coloring Problem is NP-hard, meaning that there is no known algorithm to solve it optimally in polynomial time for all instances. However, there are efficient algorithms and heuristics for finding approximate solutions.
5.What are some common algorithms for solving the Graph Coloring Problem?
Common algorithms include backtracking, greedy coloring, genetic algorithms, and constraint programming. Each has its strengths and weaknesses depending on the problem instance.