graph theory

Four mathematicians have found a new upper limit to the “Ramsey number,” a crucial property describing unavoidable structure in graphs.

The “packing coloring” problem asks how many numbers are needed to fill an infinite grid so that identical numbers never get too close to one another. A new computer-assisted proof finds a surprisingly straightforward answer.

Unpredictability can help computer scientists solve otherwise intractable problems.

The four-color problem is simple to explain, but its complex proof continues to be both celebrated and despised.

Mathematicians have struggled to understand the moduli space of graphs. A new paper uses tools from physics to peek inside.

In Shang-Hua Teng’s work, theoretical and practical questions have long been intertwined. Now he’s turning his focus to the impractical.

Researchers can now find the shortest route through a network nearly as fast as theoretically possible, even when some steps can cancel out others.

Zero-knowledge proofs allow researchers to prove their knowledge without divulging the knowledge itself.

In 1973, Paul Erdős asked if it was possible to assemble sets of “triples” — three points on a graph — so that they abide by two seemingly incompatible rules. A new proof shows it can always be done.