Graph coloring is a classic problem in computer science and discrete mathematics. It involves assigning colors to the vertices of a graph such that no two adjacent vertices share the same color. The goal is to use the minimum number of colors possible, known as the graph’s chromatic number. This article provides a C++ program that implements a backtracking algorithm to find the minimum number of colors required to color a given graph.

Program Structure

The program is structured into several key components:

• Graph Representation: The graph is represented using an adjacency matrix.
• Color Assignment: The program attempts to assign colors to vertices one by one, ensuring that no two adjacent vertices have the same color.
• Backtracking: If a color assignment leads to a conflict, the program backtracks and tries a different color.
• Optimization: The program iteratively increases the number of colors until a valid coloring is found.

Code Implementation

The following C++ program implements the graph coloring problem using a backtracking approach:

// Graph Coloring Problem in C++
// This program assigns the minimum number of colors to a graph such that
// no two adjacent vertices have the same color.

#include <iostream>
#include <vector&gt>
using namespace std;

// Function to check if the current color assignment is safe for vertex v
bool isSafe(int v, vector<vector> &graph, vector &color, int c) {
    for(int i = 0; i < graph.size(); i++) {
        if(graph[v][i] == 1 && color[i] == c)
            return false;
    }
    return true;
}

// Recursive function to solve the graph coloring problem
bool graphColoringUtil(vector<vector> &graph, int m, vector &color, int v) {
    // If all vertices are assigned a color, return true
    if(v == graph.size())
        return true;

    // Try different colors for vertex v
    for(int c = 1; c <= m; c++) {
        // Check if assignment of color c to vertex v is safe
        if(isSafe(v, graph, color, c)) {
            color[v] = c; // Assign color c to vertex v

            // Recur to assign colors to the rest of the vertices
            if(graphColoringUtil(graph, m, color, v + 1))
                return true;

            // If assigning color c doesn't lead to a solution, remove it (backtrack)
            color[v] = 0;
        }
    }

    // If no color can be assigned to vertex v, return false
    return false;
}

// Function to find the minimum number of colors needed to color the graph
int findMinColors(vector<vector> &graph) {
    int V = graph.size();
    // Initialize color assignment to 0 (no color assigned)
    vector color(V, 0);

    // Try different numbers of colors starting from 1
    for(int m = 1; m <= V; m++) {
        if(graphColoringUtil(graph, m, color, 0)) {
            return m; // Return the minimum number of colors found
        }
    }

    return V; // In the worst case, V colors are needed
}

int main() {
    // Example graph represented as an adjacency matrix
    // Number of vertices
    int V = 4;
    // Adjacency matrix
    vector<vector> graph = {
        {0, 1, 1, 1},
        {1, 0, 1, 0},
        {1, 1, 0, 1},
        {1, 0, 1, 0}
    };

    int minColors = findMinColors(graph);
    cout << "Minimum number of colors required: " << minColors << endl;

    return 0;
}
        

Program Explanation

Let’s break down the key components of the program:

1. Graph Representation

The graph is represented using an adjacency matrix, where graph[i][j] = 1 indicates an edge between vertex i and vertex j, and 0 indicates no edge.

2. isSafe Function

isSafe checks whether it’s safe to assign a particular color to a vertex. It ensures that no adjacent vertex has the same color.

bool isSafe(int v, vector<vector> &graph, vector &color, int c) {
    for(int i = 0; i < graph.size(); i++) {
        if(graph[v][i] == 1 && color[i] == c)
            return false;
    }
    return true;
}
        

3. graphColoringUtil Function

graphColoringUtil is a recursive function that attempts to assign colors to vertices one by one. If assigning a color leads to a conflict, it backtracks and tries a different color.

bool graphColoringUtil(vector<vector> &graph, int m, vector &color, 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, m, color, v + 1))
                return true;

            color[v] = 0;
        }
    }

    return false;
}
        

4. findMinColors Function

findMinColors iteratively tries increasing numbers of colors starting from 1 until a valid coloring is found.

int findMinColors(vector<vector> &graph) {
    int V = graph.size();
    vector color(V, 0);

    for(int m = 1; m <= V; m++) {
        if(graphColoringUtil(graph, m, color, 0)) {
            return m;
        }
    }

    return V;
}
        

5. main Function

The main function initializes the graph and calls findMinColors to determine the minimum number of colors required.

int main() {
    int V = 4;
    vector<vector> graph = {
        {0, 1, 1, 1},
        {1, 0, 1, 0},
        {1, 1, 0, 1},
        {1, 0, 1, 0}
    };

    int minColors = findMinColors(graph);
    cout << "Minimum number of colors required: " << minColors << endl;

    return 0;
}
        

Program Documentation

Below is the detailed documentation for each function in the program:

isSafe Function

• Purpose: To determine if it is safe to assign a specific color to a vertex.
• Parameters:
  • int v: The vertex to be colored.
  • vector<vector<int>> &graph: The adjacency matrix representing the graph.
  • vector<int> &color: The current color assignments of vertices.
  • int c: The color to be assigned.
• Returns: true if it’s safe to assign color c to vertex v, otherwise false.

graphColoringUtil Function

• Purpose: To recursively assign colors to vertices using backtracking.
• Parameters:
  • vector<vector<int>> &graph: The adjacency matrix representing the graph.
  • int m: The maximum number of colors allowed.
  • vector<int> &color: The current color assignments of vertices.
  • int v: The current vertex to be colored.
• Returns: true if a valid coloring is possible with m colors, otherwise false.

findMinColors Function

• Purpose: To find the minimum number of colors required to color the graph.
• Parameters:
  • vector<vector<int>> &graph: The adjacency matrix representing the graph.
• Returns: The minimum number of colors required to color the graph.

main Function

• Purpose: To initialize the graph and determine the minimum number of colors required.
• Process:
  • Defines the number of vertices V.
  • Initializes the adjacency matrix graph.
  • Calls findMinColors to compute the minimum colors.
  • Outputs the result.
• Returns: 0 upon successful execution.

How the Program Works

1. The program starts by defining the graph using an adjacency matrix.
2. The findMinColors function is called to determine the smallest number of colors needed.
3. findMinColors iteratively tries increasing numbers of colors, starting from 1.
4. For each number of colors m, it calls graphColoringUtil to attempt to color the graph.
5. graphColoringUtil assigns colors to vertices one by one, ensuring that no two adjacent vertices share the same color.
6. If a valid coloring is found with m colors, the function returns m as the minimum number of colors required.
7. If no valid coloring is found, the program increments m and repeats the process.
8. The result is then printed to the console.

Example Execution

Consider the following example graph with 4 vertices:

Vertex 0: Connected to Vertex 1, Vertex 2, Vertex 3
Vertex 1: Connected to Vertex 0, Vertex 2
Vertex 2: Connected to Vertex 0, Vertex 1, Vertex 3
Vertex 3: Connected to Vertex 0, Vertex 2
        

Running the program with this graph will output:

Minimum number of colors required: 3

This indicates that the graph can be colored using a minimum of 3 colors such that no two adjacent vertices share the same color.

Conclusion

Graph coloring is a fundamental problem with applications in scheduling, register allocation in compilers, and more. This C++ program demonstrates a backtracking approach to determine the minimum number of colors needed to color a graph. While the backtracking method is effective for small graphs, more efficient algorithms or heuristics may be required for larger and more complex graphs.