Chapter XII Chromatic Number

Color the map

Two adjacent regions can't share a color. The fewest distinct colors that work is the chromatic number.

The chromatic number is the minimum number of colors needed to properly color a graph:

χ (G) = min {k : V = V_{1} \cup \dots \cup V_{k}, each V_{i} independent} . (1)

Deciding whether (1) is at most k is NP-complete for every fixed k from 3 upward (Karp). Famously, planar graphs are 4-colorable (Appel–Haken 1976, computer-assisted proof) — yet deciding if a planar graph is 3-colorable is still NP-complete.

The k-coloring problem reduces to and from 3-SAT via the standard variable-clause-truth gadget. Chromatic number is also notoriously hard to approximate: no polynomial algorithm can guarantee a factor better than

n^{1 - ε} (2)

unless P = NP. The hardness gap (2) makes coloring one of the most resistant of the 21.

Figures, in plain terms

(1)

χ(G) is the chromatic number — a function that takes a graph G and returns a number. The Greek letter is "chi," pronounced "kai."

min{...} picks the smallest value satisfying the condition inside the braces. The braces are set-builder notation: "the set of values k such that..."

The condition: V = V₁ ∪ ... ∪ V_k says you can split the vertices into k disjoint groups V₁, V₂, etc., whose union is all of V. The big-∪ unions them all together (same symbol family as in chapter 6's set cover).

each Vᵢ independent means no two vertices inside one group are connected by an edge.

Reassembled: χ(G) is the smallest number of "color groups" you need so adjacent vertices end up in different groups.

(2)

Same shape as the inapproximability bound in chapter 4 — n^(1−ε) for any tiny positive ε.

For a graph on 1,000 vertices, no polynomial algorithm can guarantee an answer within a factor of ~955 of the chromatic number — under standard complexity assumptions.

Among the 21 problems, chromatic number is one of the hardest to approximate, sitting alongside maximum clique and set packing in this brutally inapproximable tier.