Fast distributed algorithms for Brooks-Vizing colourings
David A. Grable, Alessandro Panconesi · 1998
Let G be a \\Delta--regular graph with n vertices and girth at least 4 such that \\Delta AE log n. We give very simple, randomized, distributed algorithms for vertex colouring G with \\Delta=k colours in O(k + log n= log \\Delta) communication rounds, for k = O(log \\Delta). The algorithm may fail or exceed the above running time, but the probability that this happens is o(1), a quantity that goes to zero as n grows. The probabilistic analysis relies on a powerful generalization of Azuma's martingale inequality that we dub the Method of Bounded Variances.