NEAR-OPTIMAL, DISTRIBUTED EDGE-COLORING VIA THE NIBBLE METHOD

We give a distributed randomized algorithm for graph edge colouring. L et G be a Delta-regular graph with n nodes. Here we prove: If epsilon> 0 is fixed and Delta much greater than log n, the algorithm almost alw ays colours G with (1 + epsilon)Delta colours in time O(log n). If s>0 is fixed, there exists a positive constant k such that if Delta much greater than log(k) n, the algorithm almost always colours G with Delt a + Delta/ log(s) n colours in time O(log n + log(s) n log log n). By ''almost always'' we mean that the algorithm may either use more than the claimed number of colours or run longer than the claimed time, but that the probability that either of these sorts of failure occurs can be made arbitrarily close to 0. The algorithm is based on the nibble method, a probabilistic strategy introduced by Vojtech Rodl. The analy sis makes use of a powerful large deviation inequality for functions o f independent random variables. (C) 1998-Elsevier Science B.V. All rig hts reserved.