Faster $(\Delta + 1)$-Edge Coloring: Breaking the $m \sqrtn$ Time Barrier
<|reference_start|>Faster $(\Delta + 1)$-Edge Coloring: Breaking the $m \sqrtn$ Time Barrier: Vizing's theorem states that any $n$-vertex $m$-edge graph of maximum degree $\Delta$ can be {\em edge colored} using at most $\Delta + 1$ different colors [Diskret.~Analiz, '64]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in $\tilde{O}(mn)$ time. This was subsequently improved to $\tilde O(m\sqrt{n})$, independently by Arjomandi [1982] and by Gabow et al.~[1985].   In this paper we present an algorithm that computes such an edge coloring in $\tilde O(mn^{1/3})$ time, giving the first polynomial improvement for this fundamental problem in over 40 years.<|reference_end|>
@article{bhattacharya2024faster,
    title={Faster $(\Delta + 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time
  Barrier},
    author={Sayan Bhattacharya, Din Carmon, Mart'in Costa, Shay Solomon, Tianyi
  Zhang},
    journal={arXiv preprint arXiv:2405.15449},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.15449},
    primaryClass={cs.DS}
}