A Randomized Algorithm for Edge-Colouring Graphs in $O(m\sqrt{n})$ Time
Corwin Sinnamon · arXiv (Cornell University) · 2019
We present a simple randomized algorithm to edge-colour arbitrary simple graphs based on the classic decomposition strategy of Gabow et al. The algorithm uses $d+1$ colours and runs in $O(m \sqrt n)$ time with high probability.