{"id":"arxiv/2611.14513","url":"https://arxiv.org/abs/2611.14513","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms","domain":"cs.DS","source":"arxiv","authors":["Ken-ichi Kawarabayashi","Hirotaka Yoneda","Masataka Yoneda"],"reviews":0,"subject":"cs.DS","summary":"We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of $Ω(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 $Ω(n / \\log n)$ for deterministic algorithms. 2. A new upper bound of $O(n (\\log \\log n)^2…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-10","reactions":{}}