Graph Coloring

Here is a deceptively simple puzzle: paint each vertex of a graph a color so that no edge ever joins two vertices of the same color. Easy with enough colors — but what is the fewest you can get away with? That number, the chromatic number, turns out to encode some of the hardest and most useful problems in computing: how to schedule exams without conflicts, how to assign radio frequencies, even how a compiler packs variables into a CPU's registers.