Very fast parallel algorithms for approximate edge coloring

This paper presents very fast parallel algorithms for approximate edge colo ring. Let log((1)) n = log n, 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 in e dges can he edge colored with (2[log(1/4)log*(n)])(c) ([<Delta>/log(c/4) lo g*(n)])2 colors in O(log log*(n)) time using O(m + n) processors on the ERE W PRAM, where Delta is the maximum vertex degree of the graph and c is an a rbitrarily large constant. It is also shown that the graph can he edge colo red using at most [4 Delta (1+4/log log log*(Delta)) log(1/2) log*(Delta )1 colors in O(log Delta log log*(Delta)/log log log* (Delta) + log log*(n)) time using O(m + n) processors on the same model. O 2001 Elsevier Science B .V. All rights reserved.