Color every node so no two connected nodes share a color, using as FEW colors as possible. That’s graph coloring — and it’s secretly everywhere: exam timetables (no student in two at once), radio frequencies, and how compilers assign your variables to CPU registers. Finding the true minimum is famously hard, but a greedy pass gets close fast. Slide to color the graph and watch conflicts vanish.
Graph coloring assigns a color to each vertex so adjacent vertices differ, minimizing the count (the CHROMATIC NUMBER χ). Finding χ exactly is NP-hard (and even approximating it is hard), but a GREEDY pass — color each vertex with the smallest color unused by its neighbors — is proper and needs at most maxdeg+1 colors (Brooks’ theorem tightens this). It models any mutual-exclusion scheduling: exam timetabling, register allocation in compilers, radio-frequency assignment, and Sudoku. A fail-loud self-check throws unless the greedy coloring is proper and within the maxdeg+1 bound (a triangle needing 3). ◆ real graph algorithms, node-verified.
Greedy is proper but NOT minimal — its color count depends on vertex order and can exceed χ; exact chromatic number is NP-hard. The properness and maxdeg+1 bound are exact.