The Fastest Way yet to Color Graphs

[tonyarkles]

In case you haven't looked at the article, this is looking specifically at the Edge Coloring problem and not the more commonly known Vertex Coloring problem. Vertex Coloring is NP-complete unfortunately.

[erikvanoosten]

You can convert edge coloring problems into vertex coloring problems and vice versa through a simple O(n) procedure.

[phkahler]

Is this going to lead to faster compile times? Faster register allocation...

[DannyBee]

No.

In SSA, the graphs are chordal, so were already easily colorable (relatively).

Outside of SSA, this is not true, but the coloring is still not the hard part, it's the easy part.

[john-h-k]

Very few compilers actually use vertex coloring for register allocation