Online Graph Coloring for $k$-Colorable Graphs
This addresses a fundamental algorithmic challenge in graph theory and online computation, with incremental improvements over long-standing bounds.
The paper tackles the problem of online graph coloring for k-colorable graphs, achieving the first major improvement in nearly three decades by providing deterministic algorithms that use significantly fewer colors for k ≥ 5 and k = 4, and closing the gap for randomized algorithms in the k = 2 case to a factor of 1.09.
We study the problem of online graph coloring for $k$-colorable graphs. The best previously known deterministic algorithm uses $\widetilde{O}(n^{1-\frac{1}{k!}})$ colors for general $k$ and $\widetilde{O}(n^{5/6})$ colors for $k = 4$, both given by Kierstead in 1998. In this paper, we finally break this barrier, achieving the first major improvement in nearly three decades. Our results are summarized as follows: (1) $k \geq 5$ case. We provide a deterministic online algorithm to color $k$-colorable graphs with $\widetilde{O}(n^{1-\frac{1}{k(k-1)/2}})$ colors, significantly improving the current upper bound of $\widetilde{O}(n^{1-\frac{1}{k!}})$ colors. Our algorithm also matches the best-known bound for $k = 4$ ($\widetilde{O}(n^{5/6})$ colors). (2) $k = 4$ case. We provide a deterministic online algorithm to color $4$-colorable graphs with $\widetilde{O}(n^{14/17})$ colors, improving the current upper bound of $\widetilde{O}(n^{5/6})$ colors. (3) $k = 2$ case. We show that for randomized algorithms, the upper bound is $1.034 \log_2 n + O(1)$ colors and the lower bound is $\frac{91}{96} \log_2 n - O(1)$ colors. This means that we close the gap to a factor of $1.09$. With our algorithm for the $k \geq 5$ case, we also obtain a deterministic online algorithm for graph coloring that achieves a competitive ratio of $O(\frac{n}{\log \log n})$, which improves the best-known result of $O(\frac{n \log \log \log n}{\log \log n})$ by Kierstead. For the bipartite graph case ($k = 2$), the limit of online deterministic algorithms is known: any deterministic algorithm requires $2 \log_2 n - O(1)$ colors. Our results imply that randomized algorithms can perform slightly better but still have a limit.