# Nearly optimal distributed edge colouring in $O(\log \log n)$ rounds

### David A. Grable Institut für Informatik Humboldt-Universität zu Berlin Unter den Linden 6 10099 Berlin, Germany grable@informatik.hu-berlin.de Alessandro Panconesi Institut für Informatik Freie Universität Berlin Takustr. 9 14195 Berlin, Germany ale@inf.fu-berlin.de Report B 96-06 July 1996

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-96-06.ps.gz

Nearly optimal distributed edge \\colouring in $O(\log \log n)$ rounds An extremely simple distributed randomized edge colouring algorithm is given which, for any positive constants $\varepsilon$ and $c$ and a graph $G$ with minimum degree $\Omega(n^{c/\log \log n})$, produces with high probability a proper edge colouring of $G$ using $(1+\varepsilon)\Delta(G)$ colours in only $O(\log \log n)$ communication rounds.