Skip to content
doubtly

1 answer

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.

  1. Number the colours 1 to \(m\). Start with vertex 1.
  2. 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.
  3. If a valid colour is found, assign it and move to vertex \(k + 1\).
  4. If no colour is valid, backtrack to vertex \(k - 1\) and try its next colour.
  5. 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.

Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.