Online Graph Coloring for $k$-Colorable Graphs

Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda

We study the problem of online graph coloring for $k$-colorable graphs. The best previously known deterministic algorithm uses $\tilde{O}(n^{1-\frac{1}{k!}})$ colors for genera…