Even Faster $(\hat{I}”+1)$-Edge Coloring via Shorter Multi-Step Vizing Chains

Abstract

Vizing's Theorem from 1964 states that any $n$-vertex $m$-edge graph with maximum degree $\hat{I}”$ can be {\em edge colored} using at most $\hat{I}”+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 $\tilde{O}(m\sqrt{n})$. Very recently, this time bound was improved in two independent works, by Bhattacharya, Carmon, Costa, Solomon and Zhang to $\tilde{O}(m{n}^{1/3})$, and by Assadi to $\tilde{O}(n^2)$. In this paper we present an algorithm that computes such a coloring in $\tilde{O}(m{n}^{1/4})$ time. Our key technical contribution is a subroutine for extending the coloring to one more edge within time $\tilde{O}(\hat{I}{”}^2+\sqrt{\hat{I}”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 $\tilde{O}(\hat{I}{”}^6)$ by Bernshteyn [2022], dominated by the length of {\em 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 $\hat{I}”$.

To appear at SODA 2025