Near-Optimal, Distributed Edge Colouring via the Nibble Method

We give a distributed randomized algorithm to edge colour a network. Let G be a graph with n nodes and maximum degree Delta. Here we prove: If Delta = Omega(log^(1+delta) n) for some delta > 0 and lambda > 0 is fixed, the algorithm almost always colours G with (1 + lambda)Delta colours in time O(log n). If s > 0 is fixed, there exists a positive constant k such that if Delta = omega(log^k n), the algorithm almost always colours G with Delta + Delta / log^s n = (1+o(1))Delta colours in time O(logn + log^s n log log n). By "almost always" we mean that the algorithm may fail, but the failure probability can be made arbitrarily close to 0. The algorithm is based on the nibble method, a probabilistic strategy introduced by Vojtech R¨odl. The analysis makes use of a powerful large deviation inequality for functions of independent random variables.