{"ID":2838936,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.16100","arxiv_id":"2511.16100","title":"Online Graph Coloring for $k$-Colorable Graphs","abstract":"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.","short_abstract":"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, achiev...","url_abs":"https://arxiv.org/abs/2511.16100","url_pdf":"https://arxiv.org/pdf/2511.16100v2","authors":"[\"Ken-ichi Kawarabayashi\",\"Hirotaka Yoneda\",\"Masataka Yoneda\"]","published":"2025-11-20T06:45:14Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[\"LoRA\"]","has_code":false}