Online Coloring for Graphs of Large Odd Girth
This advances the theoretical understanding of online graph coloring for a specific class of graphs, but the improvement is incremental and asymptotic.
The paper improves the online coloring bound for graphs with large odd girth from O(n^{1/2}) to O(n^ε) for any ε>0, provided the odd girth is sufficiently large.
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 $\varepsilon > 0$, there exists a constant $g' \in \{3, 5, 7, \dots\}$ such that graphs with odd girth at least $g'$ can be deterministically colored online using $O(n^{\varepsilon})$ colors.