Online Coloring for Graphs of Large Odd Girth

We study the problem of online coloring for graphs with large odd girth. The best previously known algorithm uses $O(n^{1\mathrm{/}2})$ colors, which was discovered by Kierstead in 1998. This algorithm works when the odd girth is 7 or more. In this paper, we provide the following: for every $\epsilon >0$, there exists a constant $g^{\mathrm{\prime }}\in \{3,5,7,\dots \}$ such that graphs with odd girth at least $g^{\mathrm{\prime }}$ can be deterministically colored online using $O(n^{\epsilon })$ colors.