We establish new lower and upper bounds for online coloring of three‑colorable graphs, substantially improving the classic results of Vishwanathan from FOCS'1990. For deterministic algorithms the lower bound is raised from $\Omega(\log^2 n)$ to $\exp\!\bigl(\Omega((\log n)^{1/3}(\log\log n)^{2/3})\bigr)$. For randomized algorithms we present an online algorithm with expected $O(\sqrt{n})$ colors, improving the previous $O(\sqrt{n\log n})$ bound.
On the technical side, the lower‑bound construction introduces the language of $t$‑fold coloring to describe the recursion more cleanly, defines a post‑degree notion to control future vertex degrees, and exploits the two‑sided color flexibility of bipartite graphs. These are combined with Vishwanathan’s independent‑set amplification method as building blocks to guarantee three‑colorability. The upper‑bound algorithm blends ideas from offline coloring by Wigderson and Blum with Vishwanathan’s online techniques in a novel way, incorporating Wigderson’s degree control, Blum’s offline monochromatic class, Vishwanathan’s anchor sampling, and the CBIP strategy of Lovász, Saks, and Trotter.
The findings indicate that the online coloring complexity of three‑colorable graphs still admits improvement, and that the synergy of recursive constructions with randomized methods is key to further breakthroughs. Review