M-Coloring Problem
M-Coloring Problem: can the graph's vertices be colored with at most m colors so no edge joins same-colored vertices?
- 1 <= V <= 20
- 1 <= m <= V
- Graph is undirected, given as an adjacency matrix
Intuition
The m coloring problem asks whether a graph's vertices can be coloured with at most m colours so that no edge joins two vertices of the same colour. It is a decision problem — you need a yes or no, not every valid colouring.
There is no formula for the answer, so the approach is systematic search with early abandonment. Colour the vertices one at a time in a fixed order. At each vertex, try the colours in turn; a colour is legal if no already-coloured neighbour is using it.
That qualifier matters. Uncoloured neighbours impose no constraint yet — they will be checked when their own turn comes. Testing against them would be both wrong and impossible, since they have no colour to compare.
When a vertex has no legal colour at all, the problem is not with that vertex; it is that some earlier choice made this position impossible. So you undo:
- Backtrack to the previous vertex, clear its colour, and try its next option.
The search tree is exponential in the worst case, but the legality check prunes it hard — an illegal colour is rejected before any recursion happens beneath it, cutting off an entire branch. And because this is a decision problem, you return true the moment every vertex is coloured, without exploring the remaining possibilities.
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.
Approach
Before reading on: price up what the direct approach costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(mⁿ) time and O(n) space.
Colour vertices in a fixed order
Process vertex 0, then 1, and so on. Fixing the order means each recursive call is responsible for exactly one vertex, and the recursion depth equals the vertex count — a much simpler search space than choosing which vertex to colour next.
Check only already-coloured neighbours
A colour is safe for vertex v if no neighbour that already has a colour is using it. Uncoloured neighbours constrain nothing yet — they are checked when their own turn arrives, and testing them now would be meaningless.
Try each colour and recurse
For colours 1 through m, if the colour is safe, assign it and recurse on the next vertex. A true result from below means the whole graph is colourable, so propagate it up immediately without trying the remaining colours.
Undo the assignment on failure
If the recursive call returns false, clear this vertex's colour before trying the next one. Forgetting to clear leaves a stale colour that makes later safety checks reject valid options, producing a false negative rather than an error.
Report failure when no colour fits
If every colour has been tried and none led to a solution, return false so the caller can revise its own choice. Reaching the end of the vertex list, by contrast, means every vertex is coloured legally — return true.
Cost of the search
The worst case is O(mⁿ) for n vertices, since each could take any of m colours, but the safety check prunes most branches long before they are fully explored. Space is O(n) for the colour array and the recursion stack.
Solution & live demo
Common pitfalls
Not undoing the assignment on failure
color[v] = c if solve(v + 1): return True
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
return all(color[u] != c for u in range(n))
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
solve(v + 1) return True
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.
Edge cases
Greedy always succeeds; the search finds it immediately without backtracking.
Every ordering dead-ends; the search exhausts and returns False.