More Efficient Parallel $(\mathrm{\Delta }+1)$-Edge Coloring

This paper gives two parallel algorithms for $\mathrm{\Delta }+1$ edge coloring, where $\mathrm{\Delta }$ denotes the maximum degree of any vertex. The first is a deterministic parallel algorithm with $\tilde{O}({\mathrm{\Delta }}^3)$ span and $\tilde{O}(m{\mathrm{\Delta }}^3)$ work. Our second algorithm and our main result is a more efficient randomized algorithm, achieving $\tilde{O}({\mathrm{\Delta }}^2)$ span and $\tilde{O}(m{\mathrm{\Delta }}^2)$ work both with high probability. These bounds substantially improve over the recent deterministic parallel algorithm of Elkin and Khuzman, which has $\tilde{O}({\mathrm{\Delta }}^4)$ span and $\tilde{O}(m{\mathrm{\Delta }}^5)$ work. Our deterministic algorithm thus represents a $\tilde{O}(\mathrm{\Delta })$ improvement on span and $\tilde{O}({\mathrm{\Delta }}^2)$ on work compared to their algorithm, and our randomized algorithm improves the span and work by $\tilde{O}({\mathrm{\Delta }}^2)$ and $\tilde{O}({\mathrm{\Delta }}^3)$ factors, respectively. Moreover, our improvements do not come at the expense of larger logarithmic factors.