Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains

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 Õ(m √ n). Very recently, this time bound was improved in two independent works, by Bhattacharya, Carmon, Costa, Solomon and Zhang to Õ(mn 1/3 ), and by Assadi to Õ(n 2 ).

In this paper we present an algorithm that computes such a coloring in Õ(mn 1/4 ) time. Our key technical contribution is a subroutine for extending the coloring to one more edge within time Õ(∆ 2 + √ ∆n). The best previous time bound of any color extension subroutine is either the trivial O(n), dominated by the length of a Vizing chain, or the bound Õ(∆ 6 ) by Bernshteyn [2022], dominated by the length of multi-step Vizing chains, which is basically a concatenation of multiple (carefully chosen) Vizing chains. Our color extension subroutine produces significantly shorter multi-step Vizing chains than in previous works, for sufficiently large ∆.