## Algorithm of Graph Coloring using Backtracking

Graph coloring is an algorithmic technique for assigning colors to the vertices of a graph. The backtracking approach systematically explores all possibilities to find a valid coloring solution. The algorithm works by assigning colors to vertices one at a time and backtracking if a conflict arises, ensuring that adjacent vertices do not share the same color.

### Steps of the Backtracking Algorithm

**Select a Vertex**: Choose a vertex that has not yet been colored.

**Assign Colors**: Try assigning different colors to the selected vertex.

**Check for Validity**: For each color, check if it conflicts with the colors assigned to adjacent vertices.

**Backtrack**: If a conflict arises, revert to the previous vertex and try the next color.

**Repeat**: Continue the process until all vertices are colored or all options are exhausted.

### Implementation

Here’s how to implement the backtracking algorithm for graph coloring in various programming languages:

### C++

`#include <iostream>`

#include <vector>

using namespace std;

bool isSafe(int v, vector<vector<int>>& graph, vector<int>& color, int c) {

for (int i = 0; i < graph.size(); i++) {

if (graph[v][i] && color[i] == c) {

return false;

}

}

return true;

}

bool graphColoringUtil(vector<vector<int>>& graph, vector<int>& color, int m, int v) {

if (v == graph.size()) {

return true;

}

for (int c = 1; c <= m; c++) {

if (isSafe(v, graph, color, c)) {

color[v] = c;

if (graphColoringUtil(graph, color, m, v + 1)) {

return true;

}

color[v] = 0; // backtrack

}

}

return false;

}

bool graphColoring(vector<vector<int>>& graph, int m) {

vector<int> color(graph.size(), 0);

return graphColoringUtil(graph, color, m, 0);

}

int main() {

vector<vector<int>> graph = {{0, 1, 1, 1}, {1, 0, 0, 1}, {1, 0, 0, 1}, {1, 1, 1, 0}};

int m = 3; // number of colors

if (graphColoring(graph, m)) {

cout << "Graph can be colored with " << m << " colors.";

} else {

cout << "Graph cannot be colored with " << m << " colors.";

}

return 0;

}

You can also try this code with Online C++ Compiler

Run Code
### Java

`import java.util.Arrays;`

public class GraphColoring {

static boolean isSafe(int v, int graph[][], int color[], int c) {

for (int i = 0; i < graph.length; i++) {

if (graph[v][i] == 1 && color[i] == c) {

return false;

}

}

return true;

}

static boolean graphColoringUtil(int graph[][], int m, int color[], int v) {

if (v == graph.length) {

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; // backtrack

}

}

return false;

}

static boolean graphColoring(int graph[][], int m) {

int[] color = new int[graph.length];

Arrays.fill(color, 0);

return graphColoringUtil(graph, m, color, 0);

}

public static void main(String[] args) {

int graph[][] = {{0, 1, 1, 1}, {1, 0, 0, 1}, {1, 0, 0, 1}, {1, 1, 1, 0}};

int m = 3; // number of colors

if (graphColoring(graph, m)) {

System.out.println("Graph can be colored with " + m + " colors.");

} else {

System.out.println("Graph cannot be colored with " + m + " colors.");

}

}

}

You can also try this code with Online Java Compiler

Run Code
### Python

`def is_safe(v, graph, color, c):`

for i in range(len(graph)):

if graph[v][i] == 1 and color[i] == c:

return False

return True

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

if v == len(graph):

return True

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

if is_safe(v, graph, color, c):

color[v] = c

if graph_coloring_util(graph, m, color, v + 1):

return True

color[v] = 0 # backtrack

return False

def graph_coloring(graph, m):

color = [0] * len(graph)

return graph_coloring_util(graph, m, color, 0)

if __name__ == "__main__":

graph = [[0, 1, 1, 1], [1, 0, 0, 1], [1, 0, 0, 1], [1, 1, 1, 0]]

m = 3 # number of colors

if graph_coloring(graph, m):

print(f"Graph can be colored with {m} colors.")

else:

print(f"Graph cannot be colored with {m} colors.")

You can also try this code with Online Python Compiler

Run Code
### C#

`using System;`

class GraphColoring {

static bool IsSafe(int v, int[,] graph, int[] color, int c) {

for (int i = 0; i < graph.GetLength(0); i++) {

if (graph[v, i] == 1 && color[i] == c) {

return false;

}

}

return true;

}

static bool GraphColoringUtil(int[,] graph, int m, int[] color, int v) {

if (v == graph.GetLength(0)) {

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; // backtrack

}

}

return false;

}

public static bool GraphColoring(int[,] graph, int m) {

int[] color = new int[graph.GetLength(0)];

Array.Fill(color, 0);

return GraphColoringUtil(graph, m, color, 0);

}

static void Main(string[] args) {

int[,] graph = { {0, 1, 1, 1}, {1, 0, 0, 1}, {1, 0, 0, 1}, {1, 1, 1, 0} };

int m = 3; // number of colors

if (GraphColoring(graph, m)) {

Console.WriteLine($"Graph can be colored with {m} colors.");

} else {

Console.WriteLine($"Graph cannot be colored with {m} colors.");

}

}

}

Output

`Graph can be colored with 3 colors.`

**Applications of Graph Coloring:**

**Sudoku:**- This problem can also be considered a graph coloring problem. We can connect two cells with an edge if they are in the same row or same column and then color each node with no adjacent nodes having the same color.

**Bipartite Graph:**- A graph can be checked if it is a bipartite graph or not by checking if we can color a graph with two colors such that no adjacent nodes have the same color.

**Making Schedule or Time Table:**- Suppose we want to make an exam schedule for a university. We have listed different subjects and students enrolled in every subject. Many subjects would have common students (of the same batch, some backlog students, etc). How do we schedule an exam so that no two exams with a common student are scheduled at the same time? How many minimum different time slots are needed to schedule all exams? This problem can be solved using a graph where every vertex is a subject, and an edge between two vertices means there is a common student. Hence, it is a graph coloring problem where a minimum number of time slots is equal to the chromatic number of the graph.

**Register Allocation: **- In compiler optimization, Register allocation refers to assigning variables to registers and handling the transfer of data into and out of registers. This is also a graph coloring problem.

**Frequency allocation:**- The mobile towers of the same location should be assigned a different frequency. Hence, this can be solved using the graph coloring problem where towers are assumed to be nodes and two towers are connected with an edge if they are in the same location.

**Frequently Asked Questions**

### What are graph coloring algorithms?

Graph coloring algorithms assign colors to the vertices of a graph such that no two adjacent vertices share the same color, aiming to minimize the number of colors used.

### What is the approximation algorithm for graph coloring?

The approximation algorithm for graph coloring provides a near-optimal solution for coloring graphs within a certain ratio of the optimal chromatic number, especially useful for large and complex graphs.

### What is the K coloring algorithm?

The K coloring algorithm determines if a graph can be colored using K colors, ensuring adjacent vertices have different colors. It is often solved using backtracking or greedy techniques.

**Conclusion**

In this article, we discussed the concept of the chromatic number, which represents the minimum number of colors needed to color a graph. We explored the backtracking algorithm for graph coloring, outlining its steps and providing implementations in various programming languages.

If you want to learn more, check out our articles on Construct the Full K-ary Tree from its Preorder Traversal, Regular and Bipartite graphs, and Planar and Non-Planar Graphs.