Metraipolis › archive › dc_f62d670bc790
New bounds for online coloring three-colorable graphs — arXiv:2610.41516
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.41516
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T08:24:08.157Z
- SHA-256 of the archived text
4c3cb91ee06528ee0ceaef319647e4398acffdea0825164e8a3bb508db27fc45- Stable URL of this page
https://metraipolis.com/documento/dc_f62d670bc790
How to cite
New bounds for online coloring three-colorable graphs — arXiv:2610.41516 — arXiv (en), https://arxiv.org/abs/2610.41516 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f62d670bc790 (Metraipolis archive dc_f62d670bc790, sha256 4c3cb91ee06528ee0ceaef319647e4398acffdea0825164e8a3bb508db27fc45)
BibTeX
@misc{dcf62d670bc790,
title = {New bounds for online coloring three-colorable graphs — arXiv:2610.41516},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.41516},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f62d670bc790; sha256 4c3cb91ee06528ee0ceaef319647e4398acffdea0825164e8a3bb508db27fc45},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41516. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We prove new lower and upper bounds for online coloring of three-colorable graphs, improving classical bounds of Vishwanathan [FOCS'1990] that have stood for more than three decades. For the lower bound against deterministic algorithms, we improve Vishwanathan's $\Omega(\log^2n)$ to \(\exp\!\bigl(\Omega((\log n)^{1/3}(\log\log n)^{2/3})\bigr)\). For the upper bound of randomized algorithms, we give a randomized algorithm that achieves $O(\sqrt{n})$ improving Vishwanathan's $O(\sqrt{n \log n})$. Technically, for the lower bound construction, we introduce the language of $t$-fold coloring for simpler description of recursive construction, and the notion of post-degree for future control, and use the flexibility of two-sided colors of bipartite graph, constructed using the independent set amplification method of Vishwanathan, as building blocks to ensure three-colorability. The randomized algorithm integrates, in a new way, some of the ideas in offline coloring of Wigderson and Blum with ideas of Vishwanathan in the online setting, such as the degree control from Wigderson, the offline-monochromatic class from Blum, and the anchor-sampling from Vishwanathan and the CBIP algorithm by Lov{á}sz, Saks and Trotter.
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.41516 — 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-03T08:07:53.810Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).