Vizing's Theorem in Near-Linear TimeOberseminar Discrete Optimization

by Sayan Bhattacharya (University of Warwick)

Monday Jan 26, 2026, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

Vizing's theorem states that any simple graph with n nodes, m edges and maximum degree D admits a proper edge coloring with D+1 colors. Vizing's proof, dating back to 1960s, was algorithmic, and showed that such a (D+1)-edge coloring can be computed in O(mn) time. 

In this talk, I will explain how to compute a (D+1)-edge coloring in only O(m log D) time with high probability, leading to a near-optimal algorithm for this fundamental graph problem.

Joint work with Sepehr Assadi, Soheil Behnezhad, Martin Costa, Shay Solomon and Tiyani Zhang.

 

The Oberseminar takes place in the Seminarraum, 1^st floor. Participants are invited to have coffee or tea in the lounge before.