Graph Coloring on Coarse Grained Multicomputers

We present an efficient and scalable Coarse Grained Multicomputer(CGM) coloring algorithm that colors a graph G with at most \Delta + 1colors where \Delta is the maximum degree in G. This algorithm is givenin two variants: randomized and deterministic. We show that on a p-processor CGM model the proposed algorithms require a parallel time of O ( |E|p) and a total work and overall communication cost of O(|E|).These bounds correspond to the average case for the random-ized version and to the worst case for the deterministic variant