Answers are grounded in this paper and cite their sources.
We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of Ω(n / log² n) for both deterministic and randomized algorithms by Halldórsson and Szegedy (1994), (2) an upper bound of O(n / log n) for randomized algorithms by Halldórsson (1997), and (3) an upper bound of O(n / log log n) for deterministic algorithms by Kawarabayashi, Yoneda, and Yoneda (2025). In this paper, we improve these results as follows: 1. A new lower bound of Ω(n / log n) for deterministic algorithms. 2. A new upper bound of O(n (log log n)² / log² n) for randomized algorithms. 3. A new upper bound of O(n / (log log n)2-ε) for deterministic algorithms for every fixed ε>0. For randomized algorithms, we nearly close the gap between the lower and upper bounds; the remaining gap is only O((log log n)²). We establish the asymptotic separation between randomized and deterministic online graph coloring. Against an oblivious adversary, a polynomial-time randomized algorithm achieves a competitive ratio asymptotically smaller than any deterministic algorithm can guarantee, even with unlimited computation.
No takes yet. Share an insight, caveat, or question.
Kawarabayashi et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: