The Fastest Way Yet to Color Graphs

Here’s a scary scenario: You’ve been put in charge of air traffic control at Newark airport near New York. You need to make sure every plane can taxi between the runway and its gate without hitting any other planes.

Let’s bring the power of mathematics to bear on your problem. First, create a big, abstract map of your airport. For each runway, taxiway and gate, mark a point. Then, for each airplane, draw a line connecting these points: If a plane has to go from runway 4L down taxiway K to gate C80, draw a line that connects the points for runway 4L, taxiway K and gate C80.

Now for the most important part: avoiding collisions. You’ll notice that every physical location has a lot of planes coming in and out of it — a lot of lines connected to every point on your map, which researchers call a graph. To ensure that no two planes are in the same place at the same time, you can color each of your lines and require that for every point, no two lines connected to it have the same color. The colors represent times; by requiring all the colors converging at a single point to be different, you’re preventing the planes from being at the same location at the same time.

Now all you need to do is fill in the colors. In the case of an airport, it might be possible to do so by hand, even for a large airport such as Newark. But researchers commonly analyze graphs with billions or more connections. And so they’ve developed algorithms that assign colors for them.

These algorithms, however, are slow and had been “stuck more or less the same for the last 40 years,” said Sepehr Assadi, a computer scientist at the University of Waterloo in Canada.

Then, in 2024, over the space of a few days, two different groups of researchers came out with new algorithms that were significantly faster than the old standard. Now a paper to be presented in June at the 2025 Symposium on Theory of Computing goes even further. It describes a nearly optimal algorithm — one that’s practically as fast as possible. Astonishingly, this new algorithm doesn’t depend at all on the number of points in your graph, only on the number of lines. It no longer matters how large your airport is, only the number of paths taken by the planes.

This new paper “almost completely solved the problem” said Anton Bernshteyn, a mathematician at the University of California, Los Angeles. It’s “a milestone few would have predicted even a couple of years ago.”

Living on the Edge

In 1964, a mathematician named Vadim Vizing proved a shocking result: No matter how large a graph is, it’s easy to figure out how many colors you’ll need to color it. Simply look for the maximum number of lines (or edges) connected to a single point (or vertex), and add 1.

The problem of how to fill in those colors, however, proved to be a different beast. Vizing came up with his own coloring algorithm, but it was slow. He started by looking at the time it would take to color just one remaining edge of an otherwise fully colored graph. Coloring that edge could mean changing the colors of the edges adjacent to it, and changing the colors of the edges adjacent to them, and so on down the line. Vizing calculated that coloring a single edge could take — at most — an amount of time proportional to the total number of vertices, which he labeled n. If there are m edges overall, Vizing’s algorithm yields a time for coloring the entire graph that’s proportional to the product of m times n.

That value held for about 20 years until work in the 1980s brought down the edge coloring time. The new value was proportional to m times the square root of n. But the techniques behind these improvements didn’t lead to additional advances. Other researchers were unable to improve upon them any further, and progress stalled.

Then, in May 2024, Assadi posted a paper to the scientific preprint site arxiv.org that showed how to color a graph on the order of n² time — a factor that depends only on the number of vertices. For certain graphs, where the number of vertices is much smaller than the number of edges, this is a huge improvement.

Around the same time, a team unconnected to Assadi posted their own result that reduced the edge coloring time to the order of m times the cube root of n. They did it by finding a slightly faster way of coloring a single edge. In a follow-up paper, the team made a further refinement, leading to an overall runtime proportional to m times the fourth root of n.

Over the summer, the group began to collaborate with Assadi and a new team member,  Soheil Behnezhad of Northeastern University. But rather than striving for incremental improvements, they sought a more fundamental gain. “Once we found a way past that [old result],” Assadi said, “we didn’t see any fundamental barriers ahead.”

The newly formed group decided to aim for the ultimate goal: the theoretical minimum time. The fastest you can go through the entire graph and just see what it looks like — to note that this edge is red, the next one is blue and so forth — is just m, the number of edges. Since you can’t color edges faster than you can read them, that “linear time” m is the fastest possible coloring time as well.

But to reach this speed, they couldn’t rely on the same tactics they’d used in the previous papers. “We were aware that the techniques we’d introduced so far were useful to get some kind of improvement, but none of them actually had enough power to get the algorithm down to near-linear time,” said Martín Costa, a doctoral student at the University of Warwick and the coauthor of several papers on edge coloring, including last year’s advances. If they were to have any hopes of realizing that goal, Costa added, “we actually had to take a completely different approach.”

A Painting Primer

The team realized that, from the 2024 papers back to Vizing himself, all the strategies suffered from the same bottleneck. Recall that Vizing assumed the worst-case scenario — coloring the last possible edge in a graph and then having to change the colors of every other edge connected to it. “The previous work focused on trying to color that one last edge faster,” Assadi said. “So instead, we used another way.” Rather than trying to color one edge faster, they wanted to see how quickly multiple edges could be colored at virtually the same time.

To do that, the team borrowed a concept from an unlikely source: home improvement. If you’re going to repaint your walls, you first put down a coat of primer to bring them back to neutral. In the same way, the researchers tried to “prime” the graph — to bring it into a new state that made it easier to color. They used randomization techniques to do this, essentially relying on the outcomes of numerous coin tosses to color most of the graph while leaving certain edges strategically uncolored. After the priming, these last areas could be painted simply and almost simultaneously. The team’s speedy new algorithm can color a graph “near-linearly” — on the order of m times the logarithm of m.

“It’s a breakthrough — an amazing result,” said Robert Tarjan, a computer scientist at Princeton University and a winner of the Turing Award, considered the field’s highest honor. The team’s strategy of priming the graph has proved groundbreaking. “This one new idea kind of changed everything,” Tarjan said.

David Wajc, a computer scientist at the Technion in Haifa, Israel, finds the result “inspirational” — the culmination of decades of research dating back to the 1960s.

Beyond Near Perfection

Although theorists may be celebrating, it’s not yet clear if this result will translate into any real-life speedups. While theorists generally don’t care about constant factors, “in practice, they do matter,” Behnezhad noted. The runtime that they achieved is proportional to m log m or, equivalently, a constant times m log m. “In this algorithm, that constant seems to be very small,” he said. “That’s one indication that this algorithm might be practical.”

In the meantime, the group is considering how to push their result even further. The researchers would like to see if they can achieve near-linear time without relying on any randomness. “It’s theoretically interesting, and it also would be nice to know that your algorithm will always run in exactly this time, and there’s no chance that it could ever be slow,” Costa said.

In addition, the team would like to see whether it’s possible to remove that extra logarithmic term from their runtime in order to make the result not just nearly linear but exactly linear. “That is the difference between what we get and the best one can hope for,” Assadi said, “but there are very few graph problems where we can actually remove that term.”

For Tarjan, eliminating randomization and the logarithmic term would certainly be interesting, “but those are both huge challenges,” he said. “I think this result is going to be the state of the art for the foreseeable future.”