2026/07/22 by Kostas Lakis, Johannes Lengler, Adeline Pittet
#cs.DS
We study distributed vertex colouring on Hyperbolic Random Graphs (HRGs), a geometric random graph model capturing key structural features of real-world networks. This provides a natural setting for analysing distributed algorithms beyond worst-case general graphs. We introduce Sequential Radial Colouring, a CONGEST algorithm using only efficient local computation. The algorithm achieves a near-optimal palette, colouring HRGs with (4)/(3)χ colours and running in O((loglog n)2) rounds a.a.s. We also give a variant that speeds this up to O(loglog n) rounds a.a.s., at the price of using O(χloglog n) colours. Finally, for every constant ε>0, it runs in O(1) rounds a.a.s. when χ1+ε colours are used. This greatly reduces the number of colours over the previous constant-round algorithm of Maus and Ruff (SODA 2026) by a factor of at least n1/6. Our analysis contains a phase in which we consider a classical randomised colouring protocol on a (large) clique of the graph. We also delve deeper into this part of the analysis and improve upon previous results for colouring a clique C, bounding the number of rounds required as a function of the additive slack s = |Ψ| - χ, where Ψ is the set of colours used. In particular, constant-round colouring is possible if and only if s=|C|1+Ω(1), while s=|C|/log |C| already gives the optimal Θ(loglog |C|) round complexity.