Graph M-Coloring

Color every node of a graph so no two connected nodes share a color, using at most m colors. Sounds like a puzzle, and it's really a scheduling problem wearing a disguise.

Exams that share students can't run in the same slot. Radio towers that overlap can't use the same frequency. Variables alive at the same moment can't share a CPU register. In each case the things are nodes, the conflicts are edges, and the colors are whatever resource you're rationing.

A different kind of goal

Every problem so far in this section wanted all the answers. Subsets listed every subset, N-Queens counted all 92 solutions. Coloring usually just wants one answer, or a plain yes or no.

That changes the code in a way worth being deliberate about. When you're collecting everything, the recursive call returns nothing and the loop always moves on to the next choice. When you want one answer, the recursive call returns a boolean, and a success has to stop the search and travel all the way back up through every caller.

In the template that means the explore step becomes a decision instead of a plain statement: if (solve(...)) return true;. Without that, the search finds a valid coloring and then cheerfully undoes it and keeps looking, which is both slow and confusing to debug.

A trace

Five regions and three colors, colored in a fixed order, is small enough to watch the whole run happen below without a single rejection.

This example is easy enough to need no backtracking at all, which is worth seeing in itself: backtracking algorithms don't always backtrack. Drop to two colors and it becomes impossible, and the search has to exhaust every branch before it can say so.

That asymmetry is general. Proving something is possible just means finding one example. Proving it's impossible means ruling out everything, which is usually far more expensive.

Try both

Color the graph yourself, then let the solver run. Reduce the number of colors until it fails and watch how much more work the failure costs than the success did.

A free saving worth knowing

There's redundancy in this search that's easy to miss. If you find a valid coloring, swapping every red for green and every green for red gives you another valid coloring. The colors have no meaning of their own, only their pattern of agreement and disagreement matters.

So the search wastes time exploring branches that are just relabelings of each other. The standard fix is to insist that the first node always takes color 0, and more generally that a node may only use a new color once every lower-numbered color has already been used somewhere. That removes whole families of duplicate branches without losing a single genuinely distinct answer.

Symmetry breaking of this kind shows up all over search problems, and it's usually the biggest win available after the basic prune.

Why there is no clever formula

It's fair to ask whether some direct method exists that avoids searching. For 2 colors, yes: a graph is 2-colorable exactly when it has no odd-length cycle, and one traversal decides it.

From 3 colors upward, no efficient method is known. The problem is NP-complete, which in practice means that if you find a fast general algorithm for it, you've solved one of the major open problems in computer science. Until then, search with good pruning is the honest answer, and knowing that saves you from hunting for a formula that probably doesn't exist.

It also explains why the four color theorem is famous. Every map drawn on a plane needs at most four colors, a strong statement about a specific family of graphs, and it took a computer-assisted proof to establish. General graphs have no such bound.

The implementation

function color(graph, m) {
  const assigned = new Map();

  function ok(node, c) {
    for (const other of graph.neighbors(node)) {
      if (assigned.get(other) === c) return false;
    }
    return true;
  }

  function solve(index) {
    if (index === graph.nodes.length) return true;   // all done

    const node = graph.nodes[index];
    for (let c = 0; c < m; c++) {
      if (!ok(node, c)) continue;

      assigned.set(node, c);
      if (solve(index + 1)) return true;   // a success bubbles all the way up
      assigned.delete(node);               // that color failed, undo it
    }

    return false;                          // no color worked here
  }

  return solve(0) ? assigned : null;
}

Where it goes wrong

Ignoring the recursive call's return value. The single most common bug in find-one-answer problems. The solver finds a coloring, discards it, and reports failure or takes far longer than it should.

Undoing after a success. The undo belongs on the failure path only. If it runs after a successful return, the answer gets dismantled on the way back up and the caller receives an empty result.

Checking neighbors that have no color yet. Comparing against an unassigned node should never block a color. In languages where a missing key reads as a default value, an uncolored neighbor can accidentally match color 0 and rule it out everywhere.

Expecting a fast answer for large graphs. No pruning makes this problem easy in general. If your input is large and arbitrary, go look for structure in it or accept an approximate answer.

Check yourself