Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains
Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang · Society for Industrial and Applied Mathematics eBooks · 2025
Vizing’s Theorem from 1964 states that any n-vertex m-edge graph with maximum degree Δ can be edge colored using at most Δ + 1 colors. For over 40 years, the state-of-the-art running time for computing such a coloring, obtained independently by Arjomandi [1982] and by Gabow, Nishizeki, Kariv, Leven and Terada [1985], was . Very recently, this time bound was improved in two independent works, by Bhattacharya, Carmon, Costa, Solomon and Zhang to , and by Assadi to Õ (n2).