Pith. sign in

REVIEW 2 major objections 5 minor 54 references

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

T0 review · 2 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Hyperbolic random graphs can be coloured in the CONGEST model with a palette only 4/3 times the chromatic number, in O((log log n)^2) rounds.

desk verdict A real advance over Maus–Ruff: SRC/PRC get O(χ) colours in (log log n)^2 rounds for HRGs, with a genuinely new clique-slack tradeoff; the main gap is the unsupported parameter-knowledge assumption in the radius estimator. read the letter →

arxiv 2607.20360 v1 pith:ZWNB7KK4 submitted 2026-07-22 cs.DS

Kostas Lakis , Johannes Lengler , Adeline Pittet This is my paper · ORCID
classification cs.DS MSC 68W1505C1505C80
keywords distributedvertexcolouringhyperbolicrandomgraphsCONGESTmodelchromaticnumberdegeneracycolourtrialdegreeorderingclique
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes that distributed vertex colouring of hyperbolic random graphs—a realistic model of scale-free networks—can be done with a palette that is only a constant factor larger than the chromatic number χ, namely ((4/3)^α + ε)χ where α∈(1/2,1), in O((log log n)^2) rounds in the CONGEST model. The key move is to replace the maximum degree Δ by the degeneracy κ as the bottleneck: degrees in an HRG give an almost optimal ordering, and κ ≤ ((4/3)^α + o(1))χ. The algorithm, Sequential Radial Colouring, delays low-degree vertices by processing radial pseudo-bands from the centre outwards, so that colour choices of low-degree vertices never block high-degree ones. If the palette has polynomial slack χ^{1+ε}, the same framework colours in O(1) rounds. The clique-colouring analysis inside the proof also settles the exact round complexity of a classical random colour-trial protocol on a clique as a function of palette slack.

What carries the argument

The central object is the degree-based radius estimator r̂(v) = d̄⁻¹(deg(v)), which inverts the expected-degree function—strictly decreasing in radius—to place every vertex within a radial pseudo-band up to an o(1) error. The algorithm processes pseudo-bands from the centre outwards with RCTDEG (Random Colour Trial with degree priorities). The load-bearing analysis tool is the one-step failure bound: conditional on any history, a vertex remains uncoloured with probability at most (number of higher-priority uncoloured neighbours)/(available colours), which via sequential stochastic domination yields a doubly-exponential drop of the maximum uncoloured degree to O(log n) within O(log log n) rou

What would settle it

Run SRC on an HRG in which vertices are given only their own degree and not the parameters α and n; if the estimated radius deviates from the true radius by more than √δ_n = O((log n)^{-1/4}) at any band boundary, the uncoloured-degree recurrence no longer drops doubly exponentially and the O((log log n)^2) round guarantee fails. For the clique-colouring claim, attempt to colour a clique with (1+1/log n)n colours using any distributed protocol; the paper predicts Ω(log log n) rounds a.a.s., so a protocol finishing in a constant number of rounds with o(1) uncoloured vertices would refute the lo

Watch

Extended reading notes

Core claim

The paper proves Theorem 1.1: for any ε>0, with |Ψ| ≥ (1+ε)κ colours, Sequential Radial Colouring colours an HRG a.a.s. in O((log log n)^2) rounds; with |Ψ| = Ω(κ log log n), Parallel Radial Colouring uses O(log log n) rounds; and with |Ψ| ≥ κ^{1+ε}, SRC uses O(1) rounds. Since κ ≤ ((4/3)^α + o(1))χ, this yields a ((4/3)^α + ε)χ-colouring in CONGEST. The mechanism at the core is that, in an HRG, every vertex has at most (1+o(1))κ neighbours of larger degree, so the degree ordering is an almost optimal degeneracy ordering; processing bands sequentially ensures that each active vertex retains a constant-factor surplus of colours, and the maximum uncoloured degree drops doubly exponentially.

Load-bearing premise

The entire decomposition hinges on vertices recovering their radial position by inverting the expected-degree function, which requires them to know the model parameters n and α exactly; if vertices only know their own degree, the pseudo-band assignment can be wrong by more than o(1) and the phase analysis collapses (the paper states this assumption without a distributed estimation procedure).

Editorial extensions

If this is right

  • Colouring with O(χ) colours in CONGEST is possible for hyperbolic random graphs, improving the previous constant-round n^{1/6}χ-colour algorithm by a polynomial factor in palette size.
  • The degeneracy κ, not the maximum degree Δ, is identified as the natural parameter limiting distributed colouring of scale-free networks; the algorithm achieves a (1+ε)-approximation to κ arbitrarily closely.
  • The clique-colouring analysis pins down the exact round complexity of RCTDEG on a clique: Θ(log log n) rounds for (1+o(1))n colours, and constant rounds if and only if the palette has polynomial slack.
  • The O(1)-round χ^{1+ε} variant transfers a result previously known only in the LOCAL model to CONGEST with efficient local computation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the paper's conjecture χ = (1+o(1))ω (clique number) holds, the same algorithm becomes a (1+ε)-approximation to the chromatic number itself, and the 4/3 factor is an artifact of the known κ-vs-χ bounds rather than a fundamental limit.
  • A natural testable extension is whether a parameter-free version—estimating α and n from the local degree distribution instead of assuming them known—can keep the pseudo-band boundaries within the o(1) tolerance required by the radius-accuracy lemma.
  • The band-decomposition technique is not obviously limited to HRGs: any graph where the degree ordering is a near-optimal degeneracy ordering and where radial bands can be recovered from local information should exhibit the same poly-log-log colouring behaviour; this could be tested empirically on other geometric inhomogeneous random graphs or real network datasets.
  • The tight clique-colouring bounds suggest a general 'slack threshold' for random colour-trial protocols: below polynomial slack, the doubly-exponential decay phase is unavoidable, which may inform protocol design for dense subgraphs in other geometric graph models.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies distributed vertex colouring of Hyperbolic Random Graphs (HRGs) in the CONGEST model. It introduces Sequential Radial Colouring (SRC), which estimates the radial coordinate of each vertex from its degree, partitions the vertices into radial pseudo-regions, and colours these regions from the core outward using the RCTDEG protocol of Maus and Ruff. The main theorem (Theorem 1.1) claims: with (1+ε)κ colours, SRC colours the graph in O((log log n)^2) rounds a.a.s.; with O(χ log log n) colours, Parallel Radial Colouring (PRC) colours in O(log log n) rounds; and with χ^{1+ε} colours, SRC colours in O(1) rounds. Combined with the external bound κ ≤ ((4/3)^α + o(1))χ from [2], the first item yields a ((4/3)^α + ε)χ palette, motivating the '4/3χ' headline. The paper also proves sharp upper and lower bounds for RCTDEG on a clique as a function of the additive slack s = |Ψ| − |C|, using concentration inequalities for self-bounding functions.

Significance. If the result holds, it is a substantial advance over the previous CONGEST algorithm of Maus and Ruff, reducing the palette from at least n^{1/6}χ colours to O(χ) colours while keeping round complexity polyloglogarithmic, and achieving O(1) rounds with χ^{1+ε} colours. The structural message—that degeneracy κ, rather than maximum degree, is the right bottleneck for colouring HRGs—is interesting and likely to influence further work on random geometric graphs. The paper is carefully argued: the one-round domination lemma (Corollary 5.12), the pseudo-band size estimates, and the clique lower-bound analysis via self-bounding functions are explicit and checkable. No parameters are fitted to data; all statements are a.a.s. with quantified ε. The main caveats are that the radius estimator assumes knowledge of the model parameters n, α, and C, and that the PRC palette partition as described assumes knowledge of χ. These are implementation premises that need to be stated or proved. The constant 4/3 is inherited from the external structural result [2], which is legitimate.

major comments (2)
  1. [§6.1, Lemmas 6.3–6.5] The radius estimator in Section 6.1 requires vertices to know the exact expected-degree function d̄(r), which depends on the model parameters n, α, and C: Lemma 5.3 gives d̄(r) = (2α/(π(α−1/2))) n e^{−r/2} + o(...). The only implementation statement is the sentence 'We assume that the vertices known and α, which is possible to estimated' in the main text and footnote 19. No distributed estimation procedure, citation, or error analysis is provided. This is load-bearing: Lemma 6.5's guarantee |br(v)−r(v)| < √δ_n = o(1) is what allows pseudo-bands of width 1/log log n near the core to be aligned with true radial bands. A constant error in α or C changes d̄ by a constant factor and shifts the estimated radius by Θ(1), which would cross many fine-band boundaries. Lemmas 6.15, 6.17, 6.18 and Theorem 6.21 all rely on this o(1) radius accuracy. As stated, Theorem 1.1 is therefore a conditional r
  2. [§7, Theorem 7.1] The proof of PRC prescribes subpalettes of sizes ⌈(1+ε_n)χ⌉ and χ. This requires the vertices to know the chromatic number χ (or at least an asymptotic value) in order to partition the input palette. The theorem statement, however, is expressed in terms of κ, and no way to compute or estimate χ in CONGEST is given. Since the paper claims a distributed algorithm using only local computation and the input graph, this is an implementation gap. It can be fixed by describing an equal split of the given palette into O(log log n) parts and verifying the constants, possibly processing a constant number of batches sequentially, or by explicitly assuming knowledge of χ. Please make the PRC implementation independent of exact χ.
minor comments (5)
  1. [Abstract / §3] The phrase '4/3χ colours' is stronger than the actual guarantee ((4/3)^α + ε)χ stated in Section 3 and in the introduction's discussion of the interval (√(4/3), 4/3). The abstract should qualify the factor accordingly.
  2. [Table 1 and Table 4] The notation in Table 1 is garbled: '|C| 1+εn,|C| εn → ∞' should be '|C|^{1+ε_n} with |C|^{ε_n} → ∞'. Similar formatting issues appear in Table 4.
  3. [§6.1, footnote 19] The sentence 'We assume that the vertices known and α, which is possible to estimated' is grammatically garbled and should be rewritten. More importantly, this assumption should be stated in the main text and in the statement of Theorem 1.1, not only in a footnote.
  4. [References [36] and [37]] References [36] and [37] appear to have identical bibliographic data (same title, journal, volume, pages, and year). If they are intended to be two different papers, the entries need to be corrected; otherwise the duplicate should be removed.
  5. [§8.4, Lemma 8.8] The expectation bound jumps to O(n^{(1−α)(1+ε)} (log n)^{−c_in(1−α)}) without showing the intermediate algebra. The bound is quite loose and a one-line derivation would help the reader verify that the exponent is correct for every band i.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: the 4/3 constant is external ([2]), palettes are not fitted, and the main gap is an unproven parameter-knowledge premise in the radius estimator, not a circular step.

full rationale

I walked the claimed derivation chain and found no step in which an output is equivalent, by construction, to an input. Theorem 6.21 / Theorem 1.1 assume |Ψ| ≥ (1+ε)κ and prove colouring via structural lemmas (degree concentration Lemma 6.3, radius accuracy Lemma 6.5, previous-degree and internal-degree bounds Lemmas 6.15–6.17, and the band-colouring Lemma 6.18). These lemmas are derived from the Poisson HRG measure and from standard Chernoff/stochastic-domination arguments; the palette sizes are not calibrated to any observed colouring result, and the theorem quantifies over arbitrary ε>0. The constant 4/3 in the χ-bound is imported from [2] (Baguley–Maus–Ruff–Skretas), an external source, and the RCTDEG protocol is imported from [47] (Maus–Ruff), also external. The only author self-citations ([7], [19]) support background claims about diameter and typical distances and are not load-bearing for the main theorem. The closest issue is the radius estimator in Section 6.1: br(v) = dbar^{-1}(deg(v)) requires exact knowledge of n and α, and the text only says, in footnote 19, 'We assume that the vertices known and α, which is possible to estimated.' No distributed estimation protocol or error analysis is supplied. This is an unproven implementation premise and a correctness/completeness risk, but it is not circularity: dbar is defined by the model, not by the target colouring, and no inverse estimator is fitted to the colouring outcome. No equation is shown to equal another by construction, and no fitted parameter is renamed as a prediction. Accordingly, no circular step is identified; score 1 reflects only the minor self-citation and the unsupported parameter-knowledge premise, not a circular derivation.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim adds no fitted parameters; ε, K, k, xcrit, c_in are theorem/proof constants, not fitted to data. The load-bearing external inputs are the HRG model and cited structural lemmas from [2] and [47], plus the unproven algorithmic assumption that n and α are known.

assumptions (4)
  • domain assumption Hyperbolic Random Graph model: vertices from Poisson point process on disk radius R=2logn+C, edge iff hyperbolic distance ≤R (Sec 1.2).
    The theorem is stated for this model; conclusions do not transfer automatically to other graphs.
  • ad hoc to paper Vertices know n and α (and the expected-degree function) in order to compute estimated radii (Sec 6.1).
    The paper only asserts this is 'possible to estimated' without giving a procedure; Lemma 6.5 depends on exact inversion of ¯d.
  • domain assumption Prior HRG structural lemmas: κ and χ bounds from [2] (Lemmas 5.9, 5.10), larger-degree neighbourhood bound from [47, Lemma 13] (Lemma 5.6), measure/angular asymptotics from [2,35].
    These are cited, not re-derived; the 4/3χ headline constant rests on [2].
  • standard math Standard Chernoff/Poisson concentration, stochastic domination, and self-bounding concentration (McDiarmid-Reed).
    Used throughout Sections 5-9.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Distributed Colouring with 4/3 chi Colours for Hyperbolic Random Graphs." pith.science (2026). https://pith.science/paper/ZWNB7KK4

@misc{pith2026260720360,
  author       = {Pith},
  title        = {Pith review of: Distributed Colouring with 4/3 chi Colours for Hyperbolic Random Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZWNB7KK4}},
  note         = {Machine review of arXiv:2607.20360}
}
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.

Figures

Figures reproduced from arXiv: 2607.20360 by the authors.

Figure 1
Figure 1. Left: An example hyperbolic random graph for n = 500, C = 1, and α = 0.6. The red vertices form a large clique, referred to as the core. Right: Blue vertices lie in already processed inner bands and contribute to dpre(v), while green vertices lie in the active band and contribute to dint(v). The sizes of the bands in the illustration are not to scale. There are other edges incident to v, which are not depicted. The … view at source ↗
Figure 2
Figure 2. The structure of the bands. Near the pseudo-clique, the fine pseudo-bands have equal width O(1/ log log n). Farther from the centre, the coarse pseudo-bands increase in width essentially geometrically until the pseudo-outer region begins. pseudo-outer region begins at a cutoff where the relevant degrees are already small enough compared with the palette to give high constant-round success probability. Band-decomposi… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 2 linked inside Pith

  1. [2]

    Hyperbolic random graphs: Clique number and degeneracy with implications for colouring

    Samuel Baguley, Yannic Maus, Janosch Ruff, and George Skretas. Hyperbolic random graphs: Clique number and degeneracy with implications for colouring. In42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), pages 13:1–13:20, 2025

    2025

  2. [47]

    On distributed colouring of hyperbolic random graphs

    Yannic Maus and Janosch Ruff. On distributed colouring of hyperbolic random graphs. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pages 2540–2553, 2026

    2026

  3. [1]

    Four degrees of separation

    Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. Four degrees of separation. InProceedings of the 4th Annual ACM Web Science Conference (WebSci 2012), pages 33–42, 2012

    2012

  4. [3]

    Improved distributed fractional coloring algorithms

    Alkida Balliu, Fabian Kuhn, and Dennis Olivetti. Improved distributed fractional coloring algorithms. In25th International Conference on Principles of Distributed Systems (OPODIS 2021), pages 18:1–18:23, 2022

    2021

  5. [4]

    Distributed coloring of graphs with an optimal number of colors

    Étienne Bamas and Louis Esperet. Distributed coloring of graphs with an optimal number of colors. In36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), pages 10:1–10:15, 2019. 48

    2019

  6. [5]

    Deterministic distributed vertex coloring in polylogarith- mic time.Journal of the ACM, 58(5):23:1–23:25, 2011

    Leonid Barenboim and Michael Elkin. Deterministic distributed vertex coloring in polylogarith- mic time.Journal of the ACM, 58(5):23:1–23:25, 2011

    2011

  7. [6]

    A fast network-decomposition algorithm and its applications to constant-time distributed computation.Theoretical Computer Science, 751:2–23, 2018

    Leonid Barenboim, Michael Elkin, and Cyril Gavoille. A fast network-decomposition algorithm and its applications to constant-time distributed computation.Theoretical Computer Science, 751:2–23, 2018

    2018

  8. [7]

    The diameter of (threshold) geometric inhomogeneous random graphs

    Zylan Benjert, Kostas Lakis, Johannes Lengler, and Raghu Raman Ravi. The diameter of (threshold) geometric inhomogeneous random graphs. In43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026), pages 11:1–11:21, 2026

    2026

Show all 54 references
  1. [8]

    On the external validity of average-case analyses of graph algorithms.ACM Transactions on Algorithms, 20(1):1–42, 2024

    Thomas Bläsius and Philipp Fischbeck. On the external validity of average-case analyses of graph algorithms.ACM Transactions on Algorithms, 20(1):1–42, 2024

    2024

  2. [9]

    On the giant component of geometric inhomogeneous random graphs

    Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Janosch Ruff, and Ziena Zeif. On the giant component of geometric inhomogeneous random graphs. In31st Annual European Symposium on Algorithms (ESA 2023), pages 20:1–20:13, 2023

    2023

  3. [10]

    Strongly hyperbolic unit disk graphs

    Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, and Daniel Stephan. Strongly hyperbolic unit disk graphs. In40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 13:1–13:17, 2023

    2023

  4. [11]

    Hyperbolic random graphs: Separators and treewidth

    Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Hyperbolic random graphs: Separators and treewidth. In24th Annual European Symposium on Algorithms (ESA 2016), pages 15:1– 15:16, 2016

    2016

  5. [12]

    Stefano Boccaletti, Vito Latora, Yamir Moreno, Martin Chavez, and D.-U. Hwang. Complex networks: Structure and dynamics.Physics Reports, 424(4–5):175–308, 2006

    2006

  6. [13]

    Ángeles Serrano

    Marián Boguñá, Ivan Bonamassa, Manlio De Domenico, Shlomo Havlin, Dmitri Krioukov, and M. Ángeles Serrano. Network geometry.Nature Reviews Physics, 3(2):114–135, 2021

    2021

  7. [14]

    Sustaining the internet with hyperbolic mapping.Nature Communications, 1:62, 2010

    Marián Boguná, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping.Nature Communications, 1:62, 2010

    2010

  8. [15]

    Faster distributed∆-coloring via a reduction to MIS

    Yann Bourreau, Sebastian Brandt, and Alexandre Nolin. Faster distributed∆-coloring via a reduction to MIS. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pages 4481–4500, 2026

    2026

  9. [16]

    Distributed recoloring of interval and chordal graphs

    Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, and Mikaël Rabie. Distributed recoloring of interval and chordal graphs. In25th International Conference on Principles of Distributed Systems (OPODIS 2021), pages 19:1–19:17, 2022

    2021

  10. [17]

    Sampling geometric inhomogeneous random graphs in linear time

    Karl Bringmann, Ralph Keusch, and Johannes Lengler. Sampling geometric inhomogeneous random graphs in linear time. In25th Annual European Symposium on Algorithms (ESA 2017), pages 20:1–20:15, 2017

    2017

  11. [18]

    Geometric inhomogeneous random graphs.Theoretical Computer Science, 760:35–54, 2019

    Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs.Theoretical Computer Science, 760:35–54, 2019

    2019

  12. [19]

    Average distance in a general class of scale-free networks.Advances in Applied Probability, 57(2):371–406, 2025

    Karl Bringmann, Ralph Keusch, and Johannes Lengler. Average distance in a general class of scale-free networks.Advances in Applied Probability, 57(2):371–406, 2025. 49

    2025

  13. [20]

    Greedy routing and the algorithmic small-world phenomenon.Journal of Computer and System Sciences, 125:59–105, 2022

    Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, and Anisur Rahaman Molla. Greedy routing and the algorithmic small-world phenomenon.Journal of Computer and System Sciences, 125:59–105, 2022

    2022

  14. [21]

    Graph structure in the web.Computer Networks, 33(1–6):309–320, 2000

    Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, and Janet Wiener. Graph structure in the web.Computer Networks, 33(1–6):309–320, 2000

    2000

  15. [22]

    Balanced bidirectional breadth-first search on scale-free networks

    Sacha Cerf, Benjamin Dayan, Umberto De Ambroggio, Marc Kaufmann, Johannes Lengler, and Ulysse Schaller. Balanced bidirectional breadth-first search on scale-free networks. arXiv:2410.22186, 2024

    2024 arXiv

  16. [23]

    Aaron Clauset, Cosma Rohilla Shalizi, and Mark E. J. Newman. Power-law distributions in empirical data.SIAM Review, 51(4):661–703, 2009

    2009

  17. [24]

    No distributed quantum advantage for approximate graph coloring

    Xavier Coiteux-Roy, Francesco d’Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and Jukka Suomela. No distributed quantum advantage for approximate graph coloring. InProceedings of the 56th Annual A...

    2024

  18. [25]

    Location- oblivious distributed unit disk graph coloring.Algorithmica, 60:236–249, 2011

    MathieuCouture, MichelBarbeau, ProsenjitBose, PazCarmi, andEvangelosKranakis. Location- oblivious distributed unit disk graph coloring.Algorithmica, 60:236–249, 2011

    2011

  19. [26]

    Probabilistic tools for the analysis of randomized optimization heuristics

    Benjamin Doerr. Probabilistic tools for the analysis of randomized optimization heuristics. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pages 1–87. Springer, 2020

    2020

  20. [27]

    Three and a half degrees of separation

    Sergey Edunov, Smriti Bhagat, Moira Burke, Carlos Diuk, and Ismail Onur Filiz. Three and a half degrees of separation. Meta Research Blog, 2016

    2016

  21. [28]

    Distributed coloring and the local structure of unit-disk graphs.Theoretical Computer Science, 944:113674, 2023

    Louis Esperet, Sébastien Julliot, and Arnaud de Mesmay. Distributed coloring and the local structure of unit-disk graphs.Theoretical Computer Science, 944:113674, 2023

    2023

  22. [29]

    On power-law relationships of the internet topology.ACM SIGCOMM Computer Communication Review, 29(4):251–262, 1999

    Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-law relationships of the internet topology.ACM SIGCOMM Computer Communication Review, 29(4):251–262, 1999

    1999

  23. [30]

    Halldórsson, Fabian Kuhn, and Alexandre Nolin

    Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson, Fabian Kuhn, and Alexandre Nolin. Coloring fast with broadcasts. InProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2023), pages 455–465, 2023

    2023

  24. [31]

    Halldórsson, Manuel Jakob, and Yannic Maus

    Maxime Flin, Magnús M. Halldórsson, Manuel Jakob, and Yannic Maus. Sublogarithmic distributed vertex coloring with optimal number of colors. arXiv:2603.28637, 2026

    2026

  25. [32]

    Near-optimal deterministic network decomposition and ruling set, and improved MIS

    Mohsen Ghaffari and Christoph Grunau. Near-optimal deterministic network decomposition and ruling set, and improved MIS. In65th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2024), pages 2148–2179, 2024

    2024

  26. [33]

    Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition

    Mohsen Ghaffari and Fabian Kuhn. Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition. In62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2021), pages 1009–1020, 2021

    2021

  27. [34]

    From descriptive to distributed

    Jan Grebık and Zoltán Vidnyánszky. From descriptive to distributed. arXiv:2502.15347, 2025. 50

    2025 arXiv

  28. [35]

    Random hyperbolic graphs: Degree sequence and clustering

    Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random hyperbolic graphs: Degree sequence and clustering. In39th International Colloquium on Automata, Languages, and Programming (ICALP 2012), pages 573–585, 2012

    2012

  29. [37]

    Halldórsson and Christian Konrad

    Magnús M. Halldórsson and Christian Konrad. Improved distributed algorithms for coloring interval graphs with application to multicoloring trees.Theoretical Computer Science, 811:29–41, 2020

    2020

  30. [38]

    Halldórsson and Yannic Maus

    Magnús M. Halldórsson and Yannic Maus. Distributed∆-coloring under bandwidth limitations. In38th International Symposium on Distributed Computing (DISC 2024), pages 31:1–31:22, 2024

    2024

  31. [39]

    Oltvai, and Albert-László Barabási

    Hawoong Jeong, Bálint Tombor, Réka Albert, Zoltan N. Oltvai, and Albert-László Barabási. The large-scale organization of metabolic networks.Nature, 407(6804):651–654, 2000

    2000

  32. [40]

    Simple distributed∆ + 1-coloring of graphs.Information Processing Letters, 70(5):229–232, 1999

    Öjvind Johansson. Simple distributed∆ + 1-coloring of graphs.Information Processing Letters, 70(5):229–232, 1999

    1999

  33. [41]

    Richard M. Karp. The probabilistic analysis of some combinatorial search algorithms. In Algorithms and Complexity: New Directions and Recent Results, pages 1–19. Academic Press, 1976

    1976

  34. [42]

    John F. C. Kingman.Poisson Processes. Clarendon Press, 1992

    1992

  35. [43]

    On the second largest component of random hyperbolic graphs.SIAM Journal on Discrete Mathematics, 33(4):2200–2217, 2019

    Marcos Kiwi and Dieter Mitsche. On the second largest component of random hyperbolic graphs.SIAM Journal on Discrete Mathematics, 33(4):2200–2217, 2019

    2019

  36. [44]

    Distributed minimum vertex coloring and maximum independent set in chordal graphs.Theoretical Computer Science, 922:486–502, 2022

    Christian Konrad and Viktor Zamaraev. Distributed minimum vertex coloring and maximum independent set in chordal graphs.Theoretical Computer Science, 922:486–502, 2022

    2022

  37. [45]

    Hyperbolic geometry of complex networks.Physical Review E, 82(3):036106, 2010

    Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. Hyperbolic geometry of complex networks.Physical Review E, 82(3):036106, 2010

    2010

  38. [46]

    Low-diameter graph decompositions.Combinatorica, 13(4):441– 454, 1993

    Nathan Linial and Michael Saks. Low-diameter graph decompositions.Combinatorica, 13(4):441– 454, 1993

    1993

  39. [48]

    Concentration for self-bounding functions and an inequality of talagrand.Random Structures & Algorithms, 29(4):549–557, 2006

    Colin McDiarmid and Bruce Reed. Concentration for self-bounding functions and an inequality of talagrand.Random Structures & Algorithms, 29(4):549–557, 2006

    2006

  40. [49]

    Cambridge University Press, 2005

    Michael Mitzenmacher and Eli Upfal.Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005

    2005

  41. [50]

    Colouring graphs when the number of colours is almost the maximum degree.Journal of Combinatorial Theory, Series B, 109:134–195, 2014

    Michael Molloy and Bruce Reed. Colouring graphs when the number of colours is almost the maximum degree.Journal of Combinatorial Theory, Series B, 109:134–195, 2014. 51

    2014

  42. [51]

    The diameter of KPKVB random graphs.Advances in Applied Probability, 51(2):358–377, 2019

    Tobias Müller and Merlijn Staps. The diameter of KPKVB random graphs.Advances in Applied Probability, 51(2):358–377, 2019

    2019

  43. [52]

    Ángeles Serrano, Marián Boguná, and Dmitri Krioukov

    Fragkiskos Papadopoulos, Maksim Kitsak, M. Ángeles Serrano, Marián Boguná, and Dmitri Krioukov. Popularity versus similarity in growing networks.Nature, 489(7417):537–540, 2012

    2012

  44. [53]

    Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces

    Fragkiskos Papadopoulos, Dmitri Krioukov, Marián Boguná, and Amin Vahdat. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. InIEEE INFOCOM 2010, pages 1–9, 2010

    2010

  45. [54]

    Network mapping by replaying hyperbolic growth.IEEE/ACM Transactions on Networking, 23(1):198–211, 2015

    Fragkiskos Papadopoulos, Constantinos Psomas, and Dmitri Krioukov. Network mapping by replaying hyperbolic growth.IEEE/ACM Transactions on Networking, 23(1):198–211, 2015

    2015

  46. [55]

    Ángeles Serrano, Dmitri Krioukov, and Marián Boguná

    M. Ángeles Serrano, Dmitri Krioukov, and Marián Boguná. Self-similarity of complex networks and hidden metric spaces.Physical Review Letters, 100(7):078701, 2008. A Omitted proofs In this appendix we give proofs of some technical lemmas, which were omitted from the main docume...

    2008

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.