Parallel edge coloring approximation

Let G be a graph with n vertices and m edges and let its maximum degree be Δ. It is shown that a valid edge coloring of G using at most 2Δ - 1 colors can be computed in O(log n log Δ) time using O(m + n) processors on a CREW PRAM. Based on this, for any constant c > 1, a valid edge coloring for G using at most max([cΔ], Δ + 1) colors can be computed in O(log² n) time, using O(m + n) processors. Employing different techniques, we show that it is possible to compute a Δ² coloring in O(log* n) time, with O(m+n) processors. Also, a maximal matching of G can be computed in O(log² n log Δ) time using O(m + n) processors on a CREW PRAM.