Journal article · 2026 · Open access

Distributed Δ-Coloring Plays Hide-and-Seek

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti

Journal of the ACM, 73(4), 1–58 · Published 16 June 2026 · DOI 10.1145/3819817

Open full textCite this paper

In brief

“Distributed Δ-Coloring Plays Hide-and-Seek” is a 2026 journal article by Alkida Balliu and 3 co-authors, published in Journal of the ACM. OpenAlex counts 8 citations as of 17 November 2026, which puts it in the top 7% of works published in 2026 by citations. It is open access under a CC BY licence: the full text is free to read at Journal of the ACM.

Citations
8
Most cited in
2022 (3)
Field-weighted impact
7.12
References
63
Authors
4

Abstract

We prove several new tight or near-tight distributed lower bounds for classic symmetry breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any deterministic distributed algorithm that computes a Δ-coloring on Δ-regular trees requires Ω (log Δ n ) rounds and any randomized such algorithm requires Ω (log Δ log n ) rounds. We prove this by showing that a natural relaxation of the Δ-coloring problem is a fixed point in the round elimination framework. As a first application, we show that our Δ-coloring lower bound proof directly extends to arbdefective colorings. An arbdefective c -coloring of a graph G=(V,E) is given by a c -coloring of V and an orientation of E , where the arbdefect of a color i is the maximum number of monochromatic outgoing edges of any node of color i . We exactly characterize which variants of the arbdefective coloring problem can be solved in O ( f (Δ) + log * n ) rounds, for some function f , and which of them instead require Ω (log Δ n ) rounds for deterministic algorithms and Ω (log Δ log n ) rounds for randomized ones. As a second application, which we see as our main contribution, we use the structure of the fixed point as a building block to prove lower bounds as a function of Δ for problems that, in some sense, are much easier than Δ-coloring, as they can be solved in O (log * n ) deterministic rounds in bounded-degree graphs. More specifically, we prove lower bounds as a function of Δ for a large class of distributed symmetry breaking problems, which can all be solved by a simple sequential greedy algorithm. For example, we obtain novel results for the fundamental problem of computing a (2,β)-ruling set, i.e., for computing an independent set S ⊆ V such that every node v ∈ V is within distance ≤ β of some node in S . We in particular show that Ω (β Δ 1/β ) rounds are needed even if initially an O (Δ)-coloring of the graph is given. With an initial O (Δ)-coloring, this lower bound is tight and without, it still nearly matches the existing O (β Δ 2/(β +1) +log * n ) upper bound. The new (2,β)-ruling set lower bound is an exponential improvement over the best existing lower bound for the problem, which was proven in [FOCS ’20]. As a special case of the lower bound, we also obtain a…

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Balliu, A., Brandt, S., Kuhn, F., & Olivetti, D. (2026). Distributed Δ-Coloring Plays Hide-and-Seek. Journal of the ACM, 73(4), 1–58. https://doi.org/10.1145/3819817

MLA 9

Balliu, Alkida, et al. “Distributed Δ-Coloring Plays Hide-and-Seek.” Journal of the ACM, vol. 73, no. 4, 2026, pp. 1–58. https://doi.org/10.1145/3819817.

Chicago

Balliu, Alkida, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. 2026. “Distributed Δ-Coloring Plays Hide-and-Seek.” Journal of the ACM 73 (4): 1–58. https://doi.org/10.1145/3819817.

Harvard

Balliu, A. et al. (2026) ‘Distributed Δ-Coloring Plays Hide-and-Seek’, Journal of the ACM, 73(4), pp. 1–58. doi:10.1145/3819817.

IEEE

A. Balliu, S. Brandt, F. Kuhn, and D. Olivetti, “Distributed Δ-Coloring Plays Hide-and-Seek,” Journal of the ACM, vol. 73, no. 4, pp. 1–58, 2026, doi: 10.1145/3819817.

BibTeX

@article{balliu2026distributed,
  title     = {{Distributed Δ-Coloring Plays Hide-and-Seek}},
  author    = {Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Olivetti, Dennis},
  journal   = {Journal of the ACM},
  year      = {2026},
  volume    = {73},
  number    = {4},
  pages     = {1--58},
  doi       = {10.1145/3819817},
  url       = {https://doi.org/10.1145/3819817}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Citations by year

YearCitationsShare of the best year
202233
202322
202633

Its field-weighted citation impact is 7.12: it has been cited 7.12 times as often as the average work of the same field, type and year (1.00 is the world average).

Topic and keywords

Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs

  • distributed graph algorithms
  • symmetry breaking
  • maximal independent sets
  • maximal matching
  • greedy algorithm
  • randomized algorithms
  • deterministic algorithms
  • bounded degree graphs

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Balliu, A., Brandt, S., Kuhn, F., & Olivetti, D. (2026). Distributed Δ-Coloring Plays Hide-and-Seek. Journal of the ACM, 73(4), 1–58. https://doi.org/10.1145/3819817

How many times has this paper been cited?

8 times, according to OpenAlex on 17 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at Journal of the ACM: sign in and open the full text from this page.

Who wrote this paper?

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti.

What is the DOI of this paper?

10.1145/3819817, permanently at https://doi.org/10.1145/3819817. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 17 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.