Metraipolis › archive › dc_3231b28bf23f
Faster Exact Algorithms for 3- and 4-Coloring: Deterministic Improvements and Further Randomized Speedups — arXiv:2611.03115
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03115
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:59:01.859Z
- SHA-256 of the archived text
b499a9d8792349d4d52a6118abf16f09e559188b38e1f162545e7d1388e954f9- Stable URL of this page
https://metraipolis.com/documento/dc_3231b28bf23f
How to cite
Faster Exact Algorithms for 3- and 4-Coloring: Deterministic Improvements and Further Randomized Speedups — arXiv:2611.03115 — arXiv (en), https://arxiv.org/abs/2611.03115 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3231b28bf23f (Metraipolis archive dc_3231b28bf23f, sha256 b499a9d8792349d4d52a6118abf16f09e559188b38e1f162545e7d1388e954f9)
BibTeX
@misc{dc3231b28bf23f,
title = {Faster Exact Algorithms for 3- and 4-Coloring: Deterministic Improvements and Further Randomized Speedups — arXiv:2611.03115},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03115},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3231b28bf23f; sha256 b499a9d8792349d4d52a6118abf16f09e559188b38e1f162545e7d1388e954f9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03115. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study exact exponential-time algorithms for 3- and 4-coloring. For 3-coloring, the best previously published running-time bound is $O^*(1.3289^n)$, due to Eppstein (SODA 2001). We improve this bound to $O^*(1.3204^n)$ deterministically and $O^*(1.3159^n)$ using randomization. For 4-coloring, the best previously known running-time bound is $O^*(1.7159^n)$, due to Wu, Gu, Jiang, Shao, and Xu (ESA 2024). We improve this bound to $O^*(1.6975^n)$ deterministically and $O^*(1.6933^n)$ using randomization. Our algorithms for both problems combine constraint satisfaction algorithms with dynamic programming over tree and path decompositions, exploiting their complementary strengths on different graph structures. For 6-coloring, the best published randomized running-time bound is exponentially smaller than the best published deterministic bound. For 3- and 4-coloring, however, no such improvement through randomization was previously known. To the best of our knowledge, our results provide the first randomized running-time bounds for these two problems that exponentially improve upon the best previously published deterministic bounds. This raises the question of whether randomization offers an inherent exponential advantage for 3- and 4-coloring. 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/2611.03115 — 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-03T18:18:07.747Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).