But the opposite is not true, because not every graph is a line graph of some other graph.
Edit: thanks sibling reply for pointing out that it's not a bidirectional transform.
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.
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.
