Metraipolis › archive › dc_aa9ec2e34d03
Dynamic $(Δ+1)$ Vertex Coloring with Adaptive Adversaries: Entropy Compression to the Rescue — arXiv:2610.38787
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.38787
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:46:28.054Z
- SHA-256 of the archived text
5ec87c6a746999c7ca966ee13c22feb3289c39a4c6a1d2625184e2c3296ab515- Stable URL of this page
https://metraipolis.com/documento/dc_aa9ec2e34d03
How to cite
Dynamic $(Δ+1)$ Vertex Coloring with Adaptive Adversaries: Entropy Compression to the Rescue — arXiv:2610.38787 — arXiv (en), https://arxiv.org/abs/2610.38787 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_aa9ec2e34d03 (Metraipolis archive dc_aa9ec2e34d03, sha256 5ec87c6a746999c7ca966ee13c22feb3289c39a4c6a1d2625184e2c3296ab515)
BibTeX
@misc{dcaa9ec2e34d03,
title = {Dynamic $(Δ+1)$ Vertex Coloring with Adaptive Adversaries: Entropy Compression to the Rescue — arXiv:2610.38787},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.38787},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_aa9ec2e34d03; sha256 5ec87c6a746999c7ca966ee13c22feb3289c39a4c6a1d2625184e2c3296ab515},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38787. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We present a randomized algorithm for maintaining a $(\Delta+1)$ vertex coloring of a fully dynamic graph against an adaptive adversary with $\tilde{O}(\sqrt{n})$ amortized update time. Our algorithm improves upon the recent randomized algorithms of Behnezhad, Rajaraman, and Wasim (SODA 2025) with $\tilde{O}(n^{8/9})$ and Flin and Halldórsson (ICALP 2025) with $\tilde{O}(n^{2/3})$ amortized update time. Our result (nearly) matches a fundamental limit of $O(\sqrt{n})$ update time identified by Flin and Halldórsson and settles their main open question. The previous algorithms' main improvement came from efficient coloring of the dense parts of the graph. Our approach complements these prior work by handling the sparse parts more efficiently, using ideas inspired by the recently developed dynamic entropy compression method. A key new aspect of our work is to tailor this method specifically to dynamic algorithms---as opposed to original local search algorithms---and achieve update times that can be sublinear in the number of involved constraints per update.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.38787 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:17:58.593Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).