Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms

Abstract

We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of $\Omega (n/{\log }^{2}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 $\Omega (n/\log n)$ for deterministic algorithms. 2. A new upper bound of $O(n(\log \log n{)}^2/{\log }^{2}n)$ for randomized algorithms. 3. A new upper bound of $O(n/(\log \log n{)}^{2-\epsilon })$ for deterministic algorithms for every fixed $\epsilon >0$. For randomized algorithms, we nearly close the gap between the lower and upper bounds; the remaining gap is only $O((\log \log n{)}^2)$. 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.