2025/11/20 by Ken‐ichi Kawarabayashi, Kawarabayashi, Ken-ichi, H. YONEDA +2
Computer Science · #Optimization and Search Problems #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2511.16100
We study the problem of online graph coloring for k-colorable graphs. The best previously known deterministic algorithm uses \widetildeO(n1-(1)/(k!)) colors for general k and \widetildeO(n5/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 ≥ 5 case. We provide a deterministic online algorithm to color k-colorable graphs with \widetildeO(n1-(1)/(k(k-1)/2)) colors, significantly improving the current upper bound of \widetildeO(n1-(1)/(k!)) colors. Our algorithm also matches the best-known bound for k = 4 (\widetildeO(n5/6) colors). (2) k = 4 case. We provide a deterministic online algorithm to color 4-colorable graphs with \widetildeO(n14/17) colors, improving the current upper bound of \widetildeO(n5/6) colors. (3) k = 2 case. We show that for randomized algorithms, the upper bound is 1.034 log2 n + O(1) colors and the lower bound is (91)/(96) log2 n - O(1) colors. This means that we close the gap to a factor of 1.09. With our algorithm for the k ≥ 5 case, we also obtain a deterministic online algorithm for graph coloring that achieves a competitive ratio of O((n)/(log log n)), which improves the best-known result of O((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 log2 n - O(1) colors. Our results imply that randomized algorithms can perform slightly better but still have a limit.