# On a Decentralized (Delta+1)-Graph Coloring Algorithm

arXiv: https://arxiv.org/abs/1910.13900 · HTML: https://mlsanity.com/paper/1910.13900/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2019.

## Built on by (most cited first, 1 of 1)

- [Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis](https://mlsanity.com/paper/2101.12704/) (2021)

## Abstract (arXiv)

We consider a decentralized graph coloring model where each vertex only knows its own color and whether some neighbor has the same color as it. The networking community has studied this model extensively due to its applications to channel selection, rate adaptation, etc. Here, we analyze variants of a simple algorithm of Bhartia et al. [Proc., ACM MOBIHOC, 2016]. In particular, we introduce a variant which requires only O(nlogDelta) expected recolorings that generalizes the coupon collector problem. Finally, we show that the O(nDelta) bound Bhartia et al. achieve for their algorithm still holds and is tight in adversarial scenarios.