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

Jeremy T. Fineman, Seyed Ali Mohammadi

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…