Distributed Colouring with 4/3 chi Colours for Hyperbolic Random Graphs
TL;DR
This work studies distributed vertex colouring on Hyperbolic Random Graphs, a geometric random graph model capturing key structural features of real-world networks, and introduces Sequential Radial Colouring, a CONGEST algorithm using only efficient local computation.
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}\chi$ 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(\chi\log\log n)$ colours. Finally, for every constant $\varepsilon>0$, it runs in $O(1)$ rounds a.a.s. when $\chi^{1+\varepsilon}$ 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 = |\Psi| - \chi$, where $\Psi$ is the set of colours used. In particular, constant-round colouring is possible if and only if $s=|C|^{1+\Omega(1)}$, while $s=|C|/\log |C|$ already gives the optimal $\Theta(\log\log |C|)$ round complexity.