Register allocation via graph coloring: variables that are live at the same time interfere (edge). Assign registers (colors) such that no two adjacent nodes share a color. Spill if k-colorable fails.