M-Coloring Problem

Problem

Given an undirected graph and an integer M. The task is to determine if the graph can be colored with at most M colors such that no two adjacent vertices of the graph are colored with the same color. Here coloring of a graph means the assignment of colors to all vertices. Print 1 if it is possible to colour vertices and 0 otherwise. (link)

Example 1:

Input:
N = 4
M = 3
E = 5
Edges[] = {(0,1),(1,2),(2,3),(3,0),(0,2)}
Output: 1
Explanation: It is possible to colour the
given graph using 3 colours.

Example 2:

Input:
N = 3
M = 2
E = 3
Edges[] = {(0,1),(1,2),(0,2)}
Output: 0

Your Task:
Your task is to complete the function graphColoring() which takes the 2d-array graph[], the number of colours and the number of nodes as inputs and returns true if answer exists otherwise false. 1 is printed if the returned value is true, 0 otherwise. The printing is done by the driver's code.
Note: In Example there are Edges not the graph.Graph will be like, if there is an edge between vertex X and vertex Y graph[] will contain 1 at graph[X-1][Y-1], else 0. In 2d-array graph[ ], nodes are 0-based indexed, i.e. from 0 to N-1.Function will be contain 2-D graph not the edges.

Expected Time Complexity: O(M^N).
Expected Auxiliary Space: O(N).

Solution

Recursive Approach

The main concept is to attempt coloring each node with all possible colors. If we manage to color all nodes along any path, we return true; otherwise, we return false.

We begin by assigning a color to node 1, then proceed to node 2 with a different color, and continue this process up to node n. Before coloring any node, we check if it is safe to use a specific color ( x ). If it is safe, we color the node; if not, we try the next color. This method continues until all nodes are colored.

The "is safe" function determines if it is safe to color a given node ( A ) with color ( x ). It checks whether any adjacent nodes of ( A ) already have color ( x ). If they do, it is not safe; otherwise, it returns true.

We keep track of the colors of all nodes in an array, which helps in verifying the safety of coloring a node with a particular color.

We do not explore all possible combinations. Instead, we return true if we successfully color up to the ( n+1 )th node, indicating that all ( n ) nodes have been colored.

class solve {

    private boolean isSafe(boolean graph[][], int node, int col, int[] color){
        for(int i=0; i<graph.length; i++){
            if(i!=node && graph[i][node]==true && color[i]==col) return false;
        }
        return true;
    }

    private boolean solve(boolean graph[][], int m, int node, int[] color){
        if(node == graph.length) return true;

        for(int i=1; i<=m; i++){
            if(isSafe(graph, node, i, color)){
                color[node] = i;
                if(solve(graph,m,node+1,color)) return true;
                color[node] = 0;
            }
        }

        return false;
    }

    // Function to determine if graph can be coloured with at most M colours
    // such
    // that no two adjacent vertices of graph are coloured with same colour.
    public boolean graphColoring(boolean graph[][], int m, int n) {
        // Your code here
        return solve(graph, m, 0, new int[n]);
    }
}

Reference: Graph Representation

Adjacency Matrix

int[][] adjacencyMatrix = new int[V][V];
// Add edge between vertex 0 and vertex 1
adjacencyMatrix[0][1] = 1;
adjacencyMatrix[1][0] = 1;

Adjacency List

List<Integer> G[];

class Graph {
    private int V;
    private List<Integer> adj[];

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new ArrayList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }
}