我们证明了三着色图在线着色的新的下界和上界，显著提升了 Vishwanathan 在 FOCS'1990 提出的经典结果。对确定性算法的下界，从原来的 $\Omega(\log^2 n)$ 提升到 $\exp\!\bigl(\Omega((\log n)^{1/3}(\log\log n)^{2/3})\bigr)$。对随机化算法的上界，我们给出一个期望 $O(\sqrt{n})$ 的在线算法，改进了原先的 $O(\sqrt{n\log n})$。
技术上，下界构造引入 $t$ 折着色的语言以简化递归描述，定义后度（post-degree）用于控制后续顶点的度，并利用二分图的双侧颜色灵活性，结合 Vishwanathan 的独立集放大方法构造基块，确保整体三着色性。上界算法将 Wigderson 与 Blum 的离线着色思路以及 Vishwanathan 的在线技巧新颖融合，具体包括 Wigderson 的度控制、Blum 的离线单色类、Vishwanathan 的锚点采样以及 Lovász、Saks、Trotter 的 CBIP 策略。
这些结果表明，三着色图的在线着色复杂度仍有提升空间，且递归构造与随机化技术的结合是突破关键。点评