GeeksforGeeks Medium

M-Coloring Problem

Can the graph's vertices be colored with at most m colors so no edge joins same-colored vertices?

backtrackinggraph

02

Intuition

Color vertices one at a time; a color is legal if no already-colored neighbour has it. If a vertex has no legal color, backtrack — the earlier assignment forced a dead end. First full assignment = yes.

How to spot this pattern

Constraint-satisfaction backtracking: assign, verify, recurse, and undo on failure. The shape is the same as N-Queens — what changes is only the safe test. Notice it returns a boolean rather than collecting results, so the recursion can stop at the first success instead of exploring everything.

03

Approach

1

Assign vertex by vertex

At vertex v, try colors 1..m; safe checks colored neighbours only — later vertices don't constrain yet.

2

Backtrack on dead ends

If no color fits, unwind to the previous vertex and try its next color. The search tree covers all assignments but prunes hard.

3

Stop at the first success

The question is decision, not enumeration — return True the moment vertex n is passed.

04

Solution & live demo

▶1def graph_coloring(adj, m, n):     # adj: n x n matrix
▶2    color = [0] * n
▶3    def safe(v, c):
▶4        return all(not adj[v][u] or color[u] != c for u in range(n))
▶5    def solve(v):
▶6        if v == n: return True
▶7        for c in range(1, m + 1):
▶8            if safe(v, c):
▶9                color[v] = c
▶10                if solve(v + 1): return True
▶11                color[v] = 0
▶12        return False
▶13    return solve(0)

05

Common pitfalls

Not undoing the assignment on failure

✗ Wrong

color[v] = c
if solve(v + 1): return True

✓ Right

color[v] = c
if solve(v + 1): return True
color[v] = 0

A stale colour makes later branches see a constraint that was never actually committed, so valid colourings get rejected. Every assignment before a recursive call needs its inverse after.

Checking adjacency without checking the edge

✗ Wrong

return all(color[u] != c for u in range(n))

✓ Right

return all(not adj[v][u] or color[u] != c for u in range(n))

Only adjacent vertices are forbidden from sharing a colour. Comparing against every vertex demands all-distinct colours, which fails almost every solvable instance.

Ignoring the recursive return value

✗ Wrong

solve(v + 1)
return True

✓ Right

if solve(v + 1): return True

Reporting success without checking whether the rest could actually be coloured returns True for impossible instances. The answer depends on the whole assignment completing, not just this vertex.

06

Edge cases

m ≥ max degree + 1

Greedy always succeeds; the search finds it immediately without backtracking.

Complete graph with m < n

Every ordering dead-ends; the search exhausts and returns False.

07

Complexity

Time

O(mⁿ)

Space

O(n)

Exponential worst case; pruning is the practical win.