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

Abstract

This paper gives two parallel algorithms for $\Delta +1$ edge coloring, where $\Delta$ denotes the maximum degree of any vertex. The first is a deterministic parallel algorithm with $\tilde{O}({\Delta }^3)$ span and $\tilde{O}(m{\Delta }^3)$ work. Our second algorithm and our main result is a more efficient randomized algorithm, achieving $\tilde{O}({\Delta }^2)$ span and $\tilde{O}(m{\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}({\Delta }^4)$ span and $\tilde{O}(m{\Delta }^5)$ work. Our deterministic algorithm thus represents a $\tilde{O}(\Delta )$ improvement on span and $\tilde{O}({\Delta }^2)$ on work compared to their algorithm, and our randomized algorithm improves the span and work by $\tilde{O}({\Delta }^2)$ and $\tilde{O}({\Delta }^3)$ factors, respectively. Moreover, our improvements do not come at the expense of larger logarithmic factors.