# 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 graphwith 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.

Published

1996-01-11

How to Cite

*BRICS Report Series*,

*3*(11). https://doi.org/10.7146/brics.v3i11.19974

Section

Articles

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.