812. Graph m-Colouring with Backtracking

Difficulty: 5 Level: Master Assign colours to graph vertices so no two adjacent vertices share a colour — using backtracking to find valid assignments and compute the chromatic number.

The Problem This Solves

Graph colouring models any problem where conflicting entities must be assigned distinct resources. Register allocation in compilers assigns CPU registers to variables, where variables that are "live" at the same time must get different registers — this is graph colouring on the interference graph. Exam scheduling assigns time slots so that no two exams share students. Frequency assignment in wireless networks ensures adjacent cells don't interfere. Map colouring (the classic four-colour theorem) is the historical application. The chromatic number χ(G) — the minimum colours needed — characterises graph structure: χ = 1 iff no edges, χ = 2 iff bipartite, χ = 3 for planar graphs (often), χ = 5 for the Petersen graph... Computing χ is NP-complete, but backtracking works well for small graphs.

The Intuition

Try colours 0..m for each vertex in order. For each vertex, try the first colour that doesn't conflict with already-coloured neighbours. If all m colours conflict, backtrack: uncolour the current vertex and try the next colour for the previous vertex. This is classic constraint satisfaction backtracking. The `is_safe` check scans the adjacency list in O(degree). OCaml uses recursive backtracking naturally; Rust uses recursive inner functions (which must be defined as `fn` inside the outer function, since closures can't recursively call themselves without boxing). The key Rust-ism: inner `fn` items can be declared inside functions and called recursively.

How It Works in Rust

// O(m^V) worst case — backtracking with pruning
fn graph_color(adj: &[Vec<usize>], m: usize) -> Option<Vec<usize>> {
 let n = adj.len();
 let mut color = vec![usize::MAX; n];  // MAX = uncoloured

 // is_safe: check no neighbour has colour c
 fn is_safe(v: usize, c: usize, adj: &[Vec<usize>], color: &[usize]) -> bool {
     adj[v].iter().all(|&u| color[u] != c)
 }

 // Recursive backtracking: assign colour to vertex v, then recurse to v+1
 fn solve(v: usize, n: usize, m: usize, adj: &[Vec<usize>], color: &mut Vec<usize>) -> bool {
     if v == n { return true; }  // all vertices coloured: success
     for c in 0..m {
         if is_safe(v, c, adj, color) {
             color[v] = c;
             if solve(v + 1, n, m, adj, color) { return true; }
             color[v] = usize::MAX;  // backtrack
         }
     }
     false
 }

 if solve(0, n, m, adj, &mut color) { Some(color) } else { None }
}

// Find chromatic number: try m = 1, 2, 3, ... until colouring succeeds
fn chromatic_number(adj: &[Vec<usize>]) -> usize {
 let n = adj.len();
 (1..=n).find(|&m| graph_color(adj, m).is_some()).unwrap_or(n)
}
// Petersen graph → χ = 3; K5 (complete 5-graph) → χ = 5

Defining `is_safe` and `solve` as inner `fn` (not closures) allows them to be called recursively. The `adj` and `color` parameters are passed explicitly — Rust inner functions don't capture outer scope variables, unlike OCaml local functions.

What This Unlocks

Register allocation: live variable analysis produces an interference graph; graph colouring assigns registers. Spilling occurs when χ > available registers. This is how production compilers (LLVM, GCC) allocate registers.
Exam/schedule assignment: time-slot or resource assignment where conflicts (shared students, shared equipment) must be avoided — reduce to graph colouring and find a valid assignment.
Sudoku solving: Sudoku is a graph colouring problem on a 81-node graph where cells in the same row/column/box are adjacent, with m=9 colours.

Key Differences

Concept	OCaml	Rust
Recursive backtracking	Local `let rec solve v = ...` captures outer state	Inner `fn solve(...)` with explicit parameters (no capture)
Uncoloured sentinel	`None` or `-1`	`usize::MAX`
Safe check	`List.for_all (fun u -> color.(u) <> c)`	`adj[v].iter().all(\	&u\	color[u] != c)`
Chromatic number search	`let rec find m = if colorable m then m else find (m+1)`	`(1..=n).find(\	&m\	graph_color(...).is_some())`
Backtrack	Reset array element	`color[v] = usize::MAX`

// Graph m-Colouring — backtracking O(m^V)

fn graph_color(adj: &[Vec<usize>], m: usize) -> Option<Vec<usize>> {
    let n = adj.len();
    let mut color = vec![usize::MAX; n];

    fn is_safe(v: usize, c: usize, adj: &[Vec<usize>], color: &[usize]) -> bool {
        adj[v].iter().all(|&u| color[u] != c)
    }

    fn solve(v: usize, n: usize, m: usize, adj: &[Vec<usize>], color: &mut Vec<usize>) -> bool {
        if v == n { return true; }
        for c in 0..m {
            if is_safe(v, c, adj, color) {
                color[v] = c;
                if solve(v + 1, n, m, adj, color) { return true; }
                color[v] = usize::MAX;
            }
        }
        false
    }

    if solve(0, n, m, adj, &mut color) { Some(color) } else { None }
}

fn chromatic_number(adj: &[Vec<usize>]) -> usize {
    let n = adj.len();
    (1..=n).find(|&m| graph_color(adj, m).is_some()).unwrap_or(n)
}

fn main() {
    // Petersen graph — chromatic number = 3
    let n = 10;
    let mut adj = vec![vec![]; n];
    let mut add = |u: usize, v: usize| { adj[u].push(v); adj[v].push(u); };
    add(0,1); add(1,2); add(2,3); add(3,4); add(4,0); // outer
    add(5,7); add(7,9); add(9,6); add(6,8); add(8,5); // inner
    add(0,5); add(1,6); add(2,7); add(3,8); add(4,9); // spokes

    let chi = chromatic_number(&adj);
    println!("Petersen chromatic number: {chi}  (expected 3)");
    match graph_color(&adj, 3) {
        None    => println!("No 3-colouring"),
        Some(c) => println!("3-colouring: {:?}", c),
    }

    // K5: chromatic number = 5
    let adj2: Vec<Vec<usize>> = (0..5).map(|u| (0..5usize).filter(|&v| v!=u).collect()).collect();
    println!("K5 chromatic number: {}", chromatic_number(&adj2));
}

(* Graph m-Colouring — backtracking O(m^V) *)

let graph_color adj n m =
  let color = Array.make n (-1) in

  let is_safe v c =
    List.for_all (fun u -> color.(u) <> c) adj.(v)
  in

  let rec solve v =
    if v = n then true
    else
      let rec try_color c =
        if c >= m then false
        else if is_safe v c then begin
          color.(v) <- c;
          if solve (v + 1) then true
          else begin color.(v) <- -1; try_color (c + 1) end
        end
        else try_color (c + 1)
      in
      try_color 0
  in
  if solve 0 then Some (Array.copy color) else None

let chromatic_number adj n =
  let rec try_m m =
    if m > n then n
    else match graph_color adj n m with
      | Some _ -> m
      | None   -> try_m (m + 1)
  in
  try_m 1

let () =
  (* Petersen graph — chromatic number = 3 *)
  let n   = 10 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u); adj.(v) <- u :: adj.(v) in
  (* Outer 5-cycle *)
  add 0 1; add 1 2; add 2 3; add 3 4; add 4 0;
  (* Inner pentagram *)
  add 5 7; add 7 9; add 9 6; add 6 8; add 8 5;
  (* Spokes *)
  add 0 5; add 1 6; add 2 7; add 3 8; add 4 9;

  let chi = chromatic_number adj n in
  Printf.printf "Petersen graph chromatic number: %d  (expected 3)\n" chi;
  (match graph_color adj n 3 with
   | None   -> Printf.printf "No 3-colouring found\n"
   | Some c -> Printf.printf "3-colouring: [%s]\n"
       (String.concat "," (Array.to_list (Array.map string_of_int c))))