Online Coloring for Graphs of Large Odd Girth

Abstract

We study the problem of online coloring for graphs with large odd girth. The best previously known algorithm uses $O(n^{1/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^{\prime }\in \{3,5,7,\dots \}$ such that graphs with odd girth at least $g^{\prime }$ can be deterministically colored online using $O(n^{\epsilon })$ colors.