M Coloring Problem | Backtracking

geeksforgeeks.org

Problem Statement

Given an undirected graph with V vertices and M colors, determine whether it is possible to color the graph such that:

• No two adjacent vertices have the same color.
• Only M colors are available.

Return true if possible, otherwise false.

---

Brute Force Intuition

For every vertex:

Try all M colors

After coloring the entire graph:

Check whether adjacent vertices have different colors

This works but explores many invalid color assignments.

Complexity

• Time Complexity: O(M^V)
• Space Complexity: O(V)

---

Moving Towards the Optimal Approach

Instead of coloring everything first:

For each vertex:

Try every color
Check validity immediately

If valid:

Assign Color
Recurse

Else:

Try another color

---

Pattern Recognition

Whenever you see:

• Assign values under constraints
• Multiple choices per position
• Need all positions valid

Think:

Backtracking + Constraint Checking

---

Key Observation

For every node:

Can I assign Color 1 ?
Can I assign Color 2 ?
Can I assign Color 3 ?
...

If a color conflicts with a neighbour:

Reject immediately

---

Optimal Java Solution

class Solution {

    boolean graphColoring(int v, int[][] edges, int m) {

        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        int[] color = new int[v];

        return solveColoring(0, adj, color, m, v);
    }

    private boolean solveColoring(int node,
                                  ArrayList<ArrayList<Integer>> adj,
                                  int[] color,
                                  int m,
                                  int v) {

        if (node == v)
            return true;

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

            if (isSafe(node, c, adj, color)) {

                color[node] = c;

                if (solveColoring(node + 1,
                                  adj,
                                  color,
                                  m,
                                  v))
                    return true;

                color[node] = 0;
            }
        }

        return false;
    }

    private boolean isSafe(int node,
                           int currColor,
                           ArrayList<ArrayList<Integer>> adj,
                           int[] color) {

        for (int neighbour : adj.get(node)) {

            if (color[neighbour] == currColor)
                return false;
        }

        return true;
    }
}

---

Dry Run

0 ----- 1
|       |
|       |
2 ----- 3

M = 3

Coloring:

0 -> Red

1 -> Blue

2 -> Blue

3 -> Red

Valid ✅

---

Why Backtracking Works?

For every vertex:

Try all colors

If a color eventually causes a conflict:

Undo assignment
Try next color

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(M^V)
Space Complexity	O(V)

---

Interview One-Liner

Color vertices one by one, trying all possible colors while ensuring no adjacent vertices share the same color.

---

Memory Trick

Node
 ↓
Try Color
 ↓
Safe ?
 ↓
Yes → Recurse
No  → Next Color