Graph M-Coloring

Given a graph and m colours, can you colour every node so that no edge has the same colour at both ends? This is the m-coloring problem, and it is the same search you have written five times now with a different rejection test.

It also has more real uses than most puzzle problems. Register allocation in a compiler is graph colouring. So is assigning frequencies to transmitters that interfere, scheduling exams so no student sits two at once, and filling in a map so neighbouring countries look different.

Where the difficulty actually is

Deciding whether a graph can be coloured with k colours is NP-complete for every k except 0, 1 and 2. Those three are easy, and the reason 2 is easy is worth knowing.

So the jump from 2 to 3 is not a gentle increase in difficulty. It crosses from a problem with a linear-time answer to one with no known efficient answer at all. The Wikipedia article on graph coloring covers the complexity landscape, along with the four colour theorem: every planar graph can be coloured with four colours, proved by Appel and Haken in 1976 in what was the first major computer-aided proof.

Colour one yourself

Start on the map-like graph with 3 colours and the "Colour it yourself" mode. Click a node to cycle it through the colours. Broken edges turn coral.

Then switch to K4, the graph where every node touches every other, and try to do it with 3. You will get three nodes down and find the fourth has a neighbour of every available colour, every single time.

Now watch the solver on K4 with 3 colours. It grinds through every combination and reports failure, and the tree fills with coral rejections. Bump m to 4 and it succeeds almost immediately. That gap is the whole problem in miniature: proving no colouring exists means exhausting the search, while finding one that does can happen on the first path you try.

The 5-cycle is the other instructive case. Odd cycles are never bipartite, so 2 colours always fail and 3 always work.

Node order matters more than you would expect

The solver colours nodes in the order the graph lists them. That order is not part of the problem, and changing it changes how much work the search does by a large factor while changing the answer not at all.

The intuition is the same one that shows up in sudoku on the next page. A node with many already-coloured neighbours has few options left, so trying it early means failing early, near the top of the tree where a failure is cheap. A node with no coloured neighbours can take any colour, so deciding it first commits you to nothing and defers the real question.

None of these change the worst case. The problem is still NP-complete and there are graphs that defeat all of them. They change the typical case, which is what you actually run.

In code

// adj is a Map from node id to an array of neighbour ids.
function mColoring(nodes, adj, m) {
  const colors = new Map();

  function canUse(node, color) {
    for (const nb of adj.get(node) ?? []) {
      if (colors.get(nb) === color) return false;
    }
    return true;
  }

  function backtrack(i) {
    if (i === nodes.length) return true;      // every node coloured

    const node = nodes[i];
    for (let c = 0; c < m; c++) {
      if (!canUse(node, c)) continue;         // prune: a neighbour already has c

      colors.set(node, c);                    // choose
      if (backtrack(i + 1)) return true;      // explore, stop at the first success
      colors.delete(node);                    // un-choose
    }

    return false;                             // no colour worked here
  }

  return backtrack(0) ? colors : null;
}

Note the return type. Unlike the enumeration problems, this one stops at the first success and reports a boolean up the stack, because the question was whether a colouring exists rather than how many there are. Counting them all means dropping the early return and letting the loop finish.

Finding the smallest m

The smallest number of colours a graph needs is its chromatic number. The usual way to find it is to run the m-coloring decision procedure for m = 1, 2, 3 and so on, and take the first that succeeds.

That sounds wasteful and mostly is not, because the failing runs are the cheap ones. A graph that needs 4 colours fails fast at m = 1 and m = 2, does real work at m = 3 to prove impossibility, then succeeds at 4. The expensive run is the last failure, not the successes before it.

Check yourself