Suppose neighboring countries must have different colors. Replace the map with an undirected graph: each region becomes a node, and an edge connects regions that must differ. Graph coloring asks whether a given set of colors can be assigned to every node without giving adjacent nodes the same color. The colors need not be pigments; they can represent any choices that must not conflict. section 8.0 section 8.1
Four colors for South America
Argentina, Bolivia, Brazil, and Paraguay each border the other three, so they require four distinct colors. An immutable graph can represent countries as nodes and shared borders as edges. This turns a geographical question into one about node degrees and available colors. section 8.1 section 8.4
A simple recursive method works when the graph repeatedly offers a node with fewer neighbors than available colors:
- If the graph is empty, return an empty coloring. section 8.4
- Choose a node whose degree is less than the number of colors, remove it, and color the smaller graph recursively. section 8.4
- Give the removed node a color unused by its neighbors. With fewer neighbors than colors, at least one choice remains. section 8.4
Listing 8.4 The simple recursive coloring algorithm
static class SimpleGraphColoring
{
public static ImmutableDictionary<N, C>? ColorGraph<N, C>(
this ImGraph<N> graph,
ImmutableHashSet<C> colors)
where N : notnull where C : notnull
{
if (graph.IsEmpty)
return ImmutableDictionary<N, C>.Empty;
N? last = graph.Nodes
.Where(n => graph.Edges(n).Count < colors.Count)
.FirstOrDefault(); #1
if (last is null)
return null;
var coloring = graph.RemoveNode(last).ColorGraph(colors);
if (coloring is null)
return null;
var usedColors = graph.Edges(last).Select(n => coloring[n]); #2
var lastColor = colors.Except(usedColors).First(); #3
return coloring.Add(last, lastColor);
}
}
The C# implementation returns an immutable node-to-color dictionary, or null when it cannot find a low-degree node or recursively color the remainder. Null here means this method failed, not that the graph is necessarily uncolorable. section 8.4
That limitation matters. In a Sudoku graph, each of the 81 cells is a node; cells sharing a row, column, or three-by-three box are adjacent. The nine digits are colors. Every node has degree 20, so the low-degree method cannot even begin with nine colors. Backtracking search handles such graphs: track each uncolored node’s possible colors, reject a state with no valid choice, and otherwise guess a color and explore recursively. If a guess fails, try another. section 8.5 section 8.7
A proposed coloring is easy to check: inspect every edge for equal colors at its endpoints. Finding a coloring in general is harder. The graph-coloring decision problem is NP-complete, and general backtracking has exponential worst-case time. Reducing possible colors before guessing can nevertheless make practical instances manageable. section 8.5.1 section 8.7
The same conflict model appears in scheduling. A color can stand for a gate and hour assigned to an airplane, or a classroom and time slot assigned to a class. In compiler register allocation, variables with overlapping lifetimes should not receive the same register. The useful question is always which choices conflict—and whether the available choices suffice. section 8.6
