Distributed Colouring with 4/3 chi Colours for Hyperbolic Random Graphs
2026-07-22 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to color the nodes of Hyperbolic Random Graphs, which model real-world networks, in a distributed way. They develop a new algorithm called Sequential Radial Colouring that uses few colors and runs very fast, much quicker than previous methods. The paper explores trade-offs between the number of colors used and the speed of coloring, showing that fewer colors generally take more rounds. They also improve understanding of how random coloring works on cliques, detailing when fast coloring is possible based on how many extra colors are allowed. Overall, their work advances distributed coloring by leveraging the structure of these random graphs.
Hyperbolic Random GraphsDistributed vertex colouringCONGEST modelSequential Radial ColouringPalette sizeRandomised colouring protocolCliqueRound complexityAdditive slackReal-world network models
Authors
Kostas Lakis, Johannes Lengler, Adeline Pittet
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}χ$ 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(χ\log\log n)$ colours. Finally, for every constant $\varepsilon>0$, it runs in $O(1)$ rounds a.a.s. when $χ^{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 = |Ψ| - χ$, 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 $Θ(\log\log |C|)$ round complexity.