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 Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-10 Page: https://delphi.science/r/arxiv/2611.14513 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…