Graph Coloring

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

1. Select a Vertex: Choose a vertex that has not yet been colored.
    
2. Assign Colors: Try assigning different colors to the selected vertex.
    
3. Check for Validity: For each color, check if it conflicts with the colors assigned to adjacent vertices.
    
4. Backtrack: If a conflict arises, revert to the previous vertex and try the next color.
    
5. 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++
• Java
• Python
• C#

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:

1. 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.
2. 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.
3. 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. 
4. 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.
5. 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 is the rule for graph coloring?

In graph coloring, no two adjacent vertices should share the same color, ensuring proper distinction between connected vertices.

What is the three-color problem?

The three-color problem determines whether a graph can be colored using at most three colors such that no two adjacent vertices share the same color.

What is the 4-color theorem?

The 4-color theorem states that any planar graph (or map) can be colored using at most four colors, ensuring no two adjacent regions share a color.

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.