What's up in
Graph theory
Latest Articles
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.
To Pack Spheres Tightly, Mathematicians Throw Them at Random
Four mathematicians broke a 75-year-old record by finding a denser way to pack high-dimensional spheres.
Topologists Tackle the Trouble With Poll Placement
Mathematicians are using topological abstractions to find places where it’s hard to vote.