Backtracking builds a solution step by step and abandons ("backtracks" from) a partial solution as soon as it cannot lead to a valid answer. In graph colouring it assigns colours vertex by vertex and undoes a choice when no valid colour remains.
Backtracking approach
- The solution is a vector \((x_1, x_2, \dots, x_n)\) chosen one component at a time.
- The search is a depth-first traversal of a state-space tree.
- A bounding function (constraint check) is applied at each node. If the partial solution violates the constraints, that node is killed and its subtree is not explored; the algorithm goes back to the previous node and tries the next choice.
Graph colouring (m-colouring problem): colour the vertices of a graph using at most \(m\) colours so that no two adjacent vertices get the same colour.
- Number the colours 1 to \(m\). Start with vertex 1.
- For the current vertex \(k\), try colours \(1, 2, \dots, m\) in order. A colour is valid if no already-coloured adjacent vertex has it.
- If a valid colour is found, assign it and move to vertex \(k + 1\).
- If no colour is valid, backtrack to vertex \(k - 1\) and try its next colour.
- When all \(n\) vertices are coloured, a solution is found (continue backtracking to list all solutions).
mColoring(k):
repeat
NextValue(k) // next valid colour for x[k]
if x[k] == 0: return // no colour left: backtrack
if k == n: print x[1..n]
else: mColoring(k + 1)
until false
NextValue(k):
repeat
x[k] = (x[k] + 1) mod (m + 1)
if x[k] == 0: return
for j = 1 to n:
if G[k][j] == 1 and x[k] == x[j]: break
if no conflict: return
until false
Example: a 4-cycle A–B–C–D–A with \(m = 2\). A = 1, B = 2 (1 conflicts with A), C = 1, D = 2 (1 conflicts with A and C). Solution: (1, 2, 1, 2). Trying \(m = 2\) on a triangle fails at the third vertex, so backtracking proves it needs 3 colours.
Worst-case time is \(O(n\,m^{n})\), but the bounding check prunes most branches in practice.