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.

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

python

▶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

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.

06

Complexity

Time

O(mⁿ)

Space

O(n)

Exponential worst case; pruning is the practical win.