Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914439128678400 |
|---|---|
| author | Flin, Maxime Halldórsson, Magnús M. Jakob, Manuel Maus, Yannic |
| author_facet | Flin, Maxime Halldórsson, Magnús M. Jakob, Manuel Maus, Yannic |
| contents | For any $Δ$, let $k_Δ$ be the maximum integer $k$ such that $(k+1)(k+2)\le Δ$. We give a distributed \LOCAL algorithm that, given an integer $k < k_Δ$, computes a valid $Δ-k$-coloring if one exists. The algorithm runs in $\tilde{O}(\log^4 \log n)$ rounds, which is within a polynomial factor of the $Ω(\log\log n)$ lower bound, which already applies to the case $k=0$. It is also best possible in the sense that if $k \ge k_Δ$, the problem requires $Ω(n/Δ)$ distributed rounds [Molloy, Reed, '14, Bamas, Esperet '19]. For $Δ$ at most polylogarithmic, the algorithm is an exponential improvement over the current state of the art of $O(\log^{49/12} n)$ rounds. When $Δ\ge (\log n)^{50}$, our algorithm achieves an even faster runtime of $O(\log^* n)$ rounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_28637 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors Flin, Maxime Halldórsson, Magnús M. Jakob, Manuel Maus, Yannic Data Structures and Algorithms Distributed, Parallel, and Cluster Computing For any $Δ$, let $k_Δ$ be the maximum integer $k$ such that $(k+1)(k+2)\le Δ$. We give a distributed \LOCAL algorithm that, given an integer $k < k_Δ$, computes a valid $Δ-k$-coloring if one exists. The algorithm runs in $\tilde{O}(\log^4 \log n)$ rounds, which is within a polynomial factor of the $Ω(\log\log n)$ lower bound, which already applies to the case $k=0$. It is also best possible in the sense that if $k \ge k_Δ$, the problem requires $Ω(n/Δ)$ distributed rounds [Molloy, Reed, '14, Bamas, Esperet '19]. For $Δ$ at most polylogarithmic, the algorithm is an exponential improvement over the current state of the art of $O(\log^{49/12} n)$ rounds. When $Δ\ge (\log n)^{50}$, our algorithm achieves an even faster runtime of $O(\log^* n)$ rounds. |
| title | Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2603.28637 |