C++ Program to Demonstrate the Implementation of 4-Color Problem

In this article, we will explain the 4 color problem to color a graph and implement the backtracking algorithm to solve it in C++.

The 4 Color Problem

The 4-color problem states that the maximum number of colors needed to color any planar graph (or a 2D map) is four, such that no two adjacent nodes have the same color. For example, suppose that you want to color a world map, such that no two countries sharing a border have the same color. According to this theorem, the maximum number of colors needed to do this is four. Now, to understand how to use this in graphs, consider the following graph:

We can color this graph in the following way:

// Coloring the graph
Node A: Red                  Node D: Red
Node B: Green                Node E: Blue
Node C: Green									

Colors used: Red, Green, Blue; ( 3 colors )

This theorem can be only be applied to planar graphs. Planar graphs are the graphs that can be drawn on a 2D plane without any edges crossing each other. To understand why 4 color problem cannot be applied to non-planar graphs, consider a k₅ graph. In this graph, there are five vertices and all the vertices are connected to each other. Therefore, we need five different colors to color this graph.

Backtracking Approach to Solve 4 Color Problem

We can use a backtracking approach to color a graph according to the 4-color theorem. The backtracking algorithm will try to color a node with one of the four colors. If the color is valid (i.e., it does not conflict with the colors of adjacent nodes), it will proceed to the next node. If it finds the color conflicts with adjacent nodes, it will backtrack and try the next color.

Here are the steps to implement the backtracking algorithm for the 4-color problem:

• Input the graph from user in an adjacency list
• In the graph start from first node and try to color it with the the first color
• Then check the assigned color is valid, by making sure that no adjacent nodes have the same color
• If the color is valid, move to the next node and repeat the process
• If out of 4 color, no color can be assigned to the current node without conflict, backtrack to the previous node and try a different color there.
• This process should be continued until all nodes are colored or no valid coloring is possible.
• Print the colored graph

C++ Code to Solve 4 Color Problem

The code below implements the backtracking algorithm to solve the 4-color problem in C++. The isSafe function checks if it is safe to assign a color to a vertex, and the graphColoring function recursively tries to color the graph.

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

const int MAX_COLORS = 4;

// Check if it's safe to assign color c to vertex v
bool isSafe(int v, const vector<vector<int>>& adj, const vector<int>& color, int c) {
    for (int u : adj[v]) {
        if (color[u] == c) return false; // Neighbor has same color
    }
    return true;
}

// Recursive function to try coloring the graph
bool graphColoring(int v, const vector<vector<int>>& adj, vector<int>& color, int V) {
    if (v == V) return true; // All vertices are colored

    for (int c = 1; c <= MAX_COLORS; ++c) {
        if (isSafe(v, adj, color, c)) {
            color[v] = c;
            if (graphColoring(v + 1, adj, color, V)) return true;
            color[v] = 0; // Backtrack
        }
    }
    return false;
}

void solveGraphColoring(const vector<vector<int>>& adj) {
    int V = adj.size();
    vector<int> color(V, 0);

    if (!graphColoring(0, adj, color, V)) {
        cout << "Solution not possible with 4 colors.\n";
        return;
    }

    cout << "Vertex colors using 4-coloring: "<< endl;
    for (int i = 0; i < V; ++i)
        cout << "Vertex " << i << " ---> Color " << color[i] << endl;
}

int main() {
    // Example graph (planar)
    vector<vector<int>> adj = {
        {1, 3},      // Neighbors of 0
        {0, 2},      // Neighbors of 1
        {1, 3},      // Neighbors of 2
        {0, 2}       // Neighbors of 3
    };

    // Print Graph
    cout << "Graph: " << endl;
    cout << "   " << 0 << endl;
    cout << "  / \ " << endl;
    cout << " " << 1 << "   " << 3 << endl;
    cout << "  \ / " << endl;
    cout << "   " << 2 << endl;


    solveGraphColoring(adj);
    return 0;
}

The output of the above code will be:

Graph: 
   0
  / \ 
 1   3
  \ / 
   2
Vertex colors using 4-coloring: 
Vertex 0 ---> Color 1
Vertex 1 ---> Color 2
Vertex 2 ---> Color 1
Vertex 3 ---> Color 2

Time and Space Complexity

Time Complexity: The time complexity of this algorithm is O(n!), where n is the number of vertices in the graph. This is because we are trying all possible colorings of the graph, and there are n! ways to color n vertices with 4 colors.

Space Complexity: The space complexity is O(n), as we need to store the color of each vertex in a vector.