What's up in
Graph theory
Latest Articles
New Method Is the Fastest Way To Find the Best Routes
A canonical problem in computer science is to find the shortest route to every point in a network. A new approach beats the classic algorithm taught in textbooks.
Why the Key to a Mathematical Life is Collaboration
Fan Chung, who has an Erdős number of 1, discusses the importance of connection — both human and mathematical.
How Does Graph Theory Shape Our World?
Maria Chudnovsky reflects on her journey in graph theory, her groundbreaking solution to the long-standing perfect graph problem, and the unexpected ways this abstract field intersects with everyday life.
The Fastest Way Yet to Color Graphs
Researchers have devised a scheme for painting the edges of a graph that’s almost as speedy as possible.
New Proof Settles Decades-Old Bet About Connected Networks
According to mathematical legend, Peter Sarnak and Noga Alon made a bet about optimal graphs in the late 1980s. They’ve now both been proved wrong.
Years After the Early Death of a Math Genius, Her Ideas Gain New Life
A new proof extends the work of the late Maryam Mirzakhani, cementing her legacy as a pioneer of alien mathematical realms.
Math’s ‘Bunkbed Conjecture’ Has Been Debunked
It was intuitive, even obvious. It was also wrong.
Computer Scientists Establish the Best Way to Traverse a Graph
Dijkstra’s algorithm was long thought to be the most efficient way to find a graph’s best routes. Researchers have now proved that it’s “universally optimal.”
In Highly Connected Networks, There’s Always a Loop
Mathematicians show that graphs of a certain common type must contain a route that visits each point exactly once.