Online Graph Coloring for $k$-Colorable Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917381488508928 |
|---|---|
| author | Kawarabayashi, Ken-ichi Yoneda, Hirotaka Yoneda, Masataka |
| author_facet | Kawarabayashi, Ken-ichi Yoneda, Hirotaka Yoneda, Masataka |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_16100 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online Graph Coloring for $k$-Colorable Graphs Kawarabayashi, Ken-ichi Yoneda, Hirotaka Yoneda, Masataka Data Structures and Algorithms Discrete Mathematics 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. |
| title | Online Graph Coloring for $k$-Colorable Graphs |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2511.16100 |