Distributed Colouring with 4/3 chi Colours for Hyperbolic Random Graphs

Abstract

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 $\frac{4}{3}\ddot{I}‡$ colours and running in $O((\log \log n{)}^2)$ rounds a.a.s. We also give a variant that speeds this up to $O(\log \log n)$ rounds a.a.s., at the price of using $O(\ddot{I}‡\log \log n)$ colours. Finally, for every constant $\epsilon >0$, it runs in $O(1)$ rounds a.a.s. when $\ddot{I}{‡}^{1+\epsilon }$ 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 $n^{1/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=|\hat{I}¨|-\ddot{I}‡$, where $\hat{I}¨$ is the set of colours used. In particular, constant-round colouring is possible if and only if $s=|C{|}^{1+\hat{I}\text{c◯}(1)}$, while $s=|C|/\log |C|$ already gives the optimal $\hat{I}˜(\log \log |C|)$ round complexity.