Graph coloring is an algorithm used in register allocation for computing register assignments. Variables in use (live) at the same time are treated as connected nodes in a graph. The register allocator tries to color the graph using as few colors as possible, so that no adjoining nodes have the same color. If the number of colors used at any given point exceeds the number of available physical registers in the machine, spill code needs to be generated. Graph coloring is NP-hard but can be approximated in quadratic time, still making it one of the most computationally intensive algorithms in a code generation pipeline.
See also Color, Register allocation, Graph fusion, and Spilling.