Two program variables interfere if their lifetimes overlap — both are alive at the same instruction. Build the interference graph with a vertex per variable and edges between interfering pairs. Coloring this graph with k colors corresponds to assigning the variables to k registers (same color = same register). Modern CPUs have ~16 general-purpose integer registers; if χ(G) ≤ 16, no spilling is needed. Chaitin's allocator (1981) was the first major use of graph coloring in compilers and remains the model. Variants ship in GCC, LLVM, V8, and the JVM's HotSpot. The same problem also runs exam timetabling (each exam a vertex, conflict edge if a student takes both, color = time slot), frequency assignment (radio towers, color = channel), and Sudoku (cells as vertices, color = digit, with extra "all-different" constraints).
36
Register allocation
When javac (or any compiler) decides which variable lives in which CPU register, it is graph-coloring the interference graph.