A Randomized Algorithm for Edge-Colouring Graphs in O(m√(n)) Time

07/06/2019

∙

by   Corwin Sinnamon, et al.

∙

0

∙

share

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.