Near-Optimal, Distributed Edge Colouring via the Nibble Method

Abstract

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.