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 . Here we prove:
The algorithm is based on the nibble method, a probabilistic strategy introduced by Vojtech Rödl. The analysis makes use of a powerful large deviation inequality for functions of independent random variables.