Assign every vertex of a graph one of k colors so that no edge ever joins two
vertices of the same color — that's the whole problem, and it's the abstract shape behind several
very concrete scheduling questions. A compiler's register allocator treats each program variable as
a vertex and draws an edge between any two variables that are ever "alive" at the same time; coloring
that conflict graph with a fixed number of colors, one per physical register, is exactly register
allocation, since two variables sharing a color means they never need the register at the same
moment. Exam timetabling is the same shape with "edge" meaning "these two exams share a student" and
"color" meaning "time slot." Like N-Queens and
Sudoku, there's no formula and no greedy rule guaranteed to
find the fewest colors — Greedy Coloring covers the
fast one-pass alternative, and what it gives up to get there. Finding the true minimum still needs
the same backtracking discipline those two pages already use, applied here unchanged: build
the assignment one vertex at a time, reject a color the instant it conflicts with an
already-colored neighbor, and back up the moment nothing further is possible.
The graph below is a small wheel: a hub vertex H connected to five rim vertices A–E, which are themselves connected in a cycle (A–B–C–D–E–A). Pick how many colors are available, then press Step or Run to watch the search work through a fixed vertex order — H first, then A through E around the rim. For the vertex currently being colored, the demo tries color 1 upward: a color is rejected the instant an already-colored neighbor already holds it, a color that survives gets placed, and the search backtracks — undoes that vertex's color and tries the next one — the moment every color up to the chosen count has been rejected in turn. Each vertex's own label doubles as its assigned color number once one is placed (for example "A·2"), so nothing has to be inferred from the fill color alone.
Checking whether color c is safe for vertex v costs
O(degree(v)) — look at v's already-colored neighbors and see whether any of
them already hold c — cheap next to the naive alternative of assigning every vertex a
color independently and only checking the whole graph for conflicts at the very end. That naive
approach on this six-vertex graph would enumerate every one of k6 full
assignments before ever checking an edge: 729 for k = 3, 4,096 for k = 4.
Backtracking never builds most of those, because a bad choice at the hub or an early rim vertex is
caught and abandoned before the remaining vertices are even considered — the demo's own attempt
counts make the gap concrete: with k = 3 the search explores only 84
color attempts (27 backtracks) before correctly concluding that no valid coloring exists at all, and
with k = 4 it finds a complete, valid coloring in just 15 attempts and
zero backtracks.
The reason k = 3 fails here isn't arbitrary — it's exactly what the graph's own
structure demands. The hub touches every rim vertex, so whichever color the hub takes, none of the
five rim vertices may reuse it, leaving only k − 1 colors free for the rim's own
five-vertex cycle. A cycle with an odd number of vertices can never be properly 2-colored — walk
around it alternating colors and the last vertex clashes with the first, since five is odd — so the
rim alone needs at least 3 colors of its own, and combined with the hub's color that's a minimum of 4
colors total. This graph's chromatic number — the smallest k for which
a valid coloring exists at all — is exactly 4, confirmed here by an independent brute-force search
across k = 1..6 (not just by this backtracking demo failing at k = 3 and
succeeding at k = 4).
function graphColor(adjacency, k) {
const n = adjacency.length;
const color = new Array(n).fill(-1);
function safe(v, c) {
return adjacency[v].every(neighbor => color[neighbor] !== c);
}
function assign(idx, order) {
if (idx === order.length) return true;
const v = order[idx];
for (let c = 0; c < k; c++) {
if (!safe(v, c)) continue;
color[v] = c;
if (assign(idx + 1, order)) return true;
color[v] = -1; // backtrack: undo, try the next color
}
return false;
}
const order = adjacency.map((_, i) => i); // any fixed vertex order works
return assign(0, order) ? color : null;
}Failing at one k doesn't mean no coloring exists — only that this k doesn't have one.
A k-coloring search answers one specific decision question at a time: "is this graph colorable with
exactly this many colors?" The demo's own default makes the distinction concrete rather than just
asserting it — switch the selector from 3 to 4 on the identical graph and the same algorithm that just
exhausted every option now succeeds quickly. A caller that wants the true chromatic number has to run
this search repeatedly at increasing k (or use a smarter bound) — one failed run at a
fixed k never means the graph is uncolorable outright.
Vertex order changes the work, not the answer. Starting the identical search from
a rim vertex instead of the hub still correctly reports k = 3 as impossible on this
graph, but takes real, measured longer to get there — 228 attempts and 75 backtracks instead of 84
and 27, because it has to rediscover the rim's own inconsistency several different ways before ever
reaching the hub and revealing why. Same graph, same k, same correct answer, more than twice the
work — checked by running the identical algorithm with only the visit order changed, the same kind
of order-sensitivity Sudoku's own Pitfalls section
already raises about its own cell order (measured there too: reading order vs. MRV cell choice
changes Sudoku's attempt count by orders of magnitude on the identical puzzle).
N-Queens' own search always fills columns in the
same fixed left-to-right order, so it has no order variant to compare — its three Pitfalls are the
missing-diagonal-check bug, the load-bearing queens.pop(), and the non-monotonic
solution count as N grows, not an order effect.
This isn't "just needs a working search" the way N-Queens and Sudoku are. General
k-coloring for k ≥ 3 is NP-complete: unlike N-Queens or Sudoku, no
algorithm — backtracking or otherwise — is known to solve every instance in polynomial time, and none
is expected to exist. The one exception is k = 2: 2-colorability is exactly
bipartiteness, and checking whether a graph is bipartite is easy — a single
BFS or DFS two-coloring pass in
O(V + E), no backtracking or trial-and-error required at all. This demo's own search
doesn't special-case k = 2 — it just runs the same general backtracking loop with only
two colors available, which is why the k = 2 case above still shows real attempts and
backtracks (10 and 4) instead of resolving instantly the way a dedicated bipartiteness check would.
Time: exponential in the worst case, the same headline as N-Queens and Sudoku —
pruning cuts the constant factor dramatically (see the attempt counts above) but doesn't change the
underlying order, and for k ≥ 3 there's no known polynomial algorithm and none is
believed to exist, since the problem is NP-complete. Space: O(V) for the
color array and the recursion stack, since only one vertex's worth of in-progress state is ever held
per recursive call.
This is the site's third Backtracking entry, closing the forward reference both N-Queens' and Sudoku's own Complexity sections named — the identical "fill the next open slot, reject a conflict immediately, undo on the way back out" shape, just with graph vertices and their neighbors standing in for board columns and rows. See Choosing a Backtracking Strategy for how this page's own k = 2 vs. k ≥ 3 split — bipartiteness is easy, general coloring is NP-complete — compares to the other nine entries.