At least GCC appears to use a graph coloring algorithm. LLVM seems to have moved from linear scan to a custom algorithm in version 3; I have no idea what they're using nowadays.
LLVM now uses something they call the "Greedy Register Allocator". As far as I can tell, it's a variation on the linear allocator with some heuristics. Here's a presentation: https://www.youtube.com/watch?v=hf8kD-eAaxg