Very fast parallel algorithms for approximate edge coloring

This paper presents very fast parallel algorithms for approximate edge coloring. Let log⁽¹⁾n=logn,log^(k)n=log(log^(k-1)n), and log*(n)=min{k|log^(k)n<1}. It is shown that a graph with n vertices and m edges can be edge colored with (2⌈log^1/4log*(n)⌉) ^c·(⌈Δ/log^c/4log*(n)⌉) ² colors in O(loglog*(n)) time using O(m+n) processors on the EREW PRAM, where Δ is the maximum vertex degree of the graph and c is an arbitrarily large constant. It is also shown that the graph can be edge colored using at most ⌈4Δ^{1+4/logloglog*(Δ)}log ^1/2log*(Δ)⌉ colors in O(logΔloglog*(Δ)/logloglog*(Δ)+loglog*(n)) time using O(m+n) processors on the same model.