The Fastest Way yet to Color Graphs
9 comments
·May 13, 2025tonyarkles
erikvanoosten
You can convert edge coloring problems into vertex coloring problems and vice versa through a simple O(n) procedure.
meindnoch
Wrong. You can convert edge-coloring problems into vertex-coloring problems of the so-called line graph: https://en.m.wikipedia.org/wiki/Line_graph
But the opposite is not true, because not every graph is a line graph of some other graph.
tonyarkles
Hrm... right. It's been a while. And it looks like both Vertex Coloring and Edge Coloring are both NP-complete (because of the O(n) procedure you're talking about and the ability to reduce both problems down to 3-SAT). I've started looking closer at the actual paper to try to figure out what's going on here. Thanks for the reminder, I miss getting to regularly work on this stuff.
Edit: thanks sibling reply for pointing out that it's not a bidirectional transform.
mauricioc
For the edge-coloring problem, the optimal number of colors needed to properly color the edges of G is always either Delta(G) (the maximum degree of G) or Delta(G) + 1, but deciding which one is the true optimum is an NP-complete problem.
Nevertheless, you can always properly edge-color a graph with Delta(G) + 1 colors. Finding such a coloring could in principle be slow, though: the original proof that Delta(G) + 1 colors is always doable amounted to a O(e(G) * v(G)) algorithm, where e(G) and v(G) denote the number of edges and vertices of G, respectively. This is polynomial, but nowhere near linear. What the paper in question shows is how, given any graph G, to find an edge coloring using Delta(G) + 1 colors in O(e(G) * log(Delta(G))) time, which is linear time if the maximum degree is a constant.
phkahler
Is this going to lead to faster compile times? Faster register allocation...
john-h-k
Very few compilers actually use vertex coloring for register allocation
isaacimagine
Totally. The hard part isn't coloring (you can use simple heuristics to get a decent register assignment), rather, it's figuring out which registers to spill (don't spill registers in hot loops! and a million other things!).
NooneAtAll3
and this post isn't even about vertex coloring
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.