Online Graph Coloring with Random Arrivals

We study online graph coloring in the random-arrival model, where the vertices are presented in a uniformly random order. Assuming $n$ and $k$ are known in advance, we present a randomized exponential-time algorithm that colors any $k$-colorable graph on $n$ vertices with $O(k^3{\log }^{2}k{\log }^{4}n)$ colors in expectation. This is the first online coloring algorithm that uses a polylogarithmic number of colors for all fixed $k\ge 3$, and is better than a known lower bound of $\mathrm{\Omega }({\log }^{k-1}n)$ colors under adversarial arrivals for all fixed $k\ge 6$. In addition, assuming $n$ is known in advance, we obtain a competitive ratio of $\tilde{O}(n^{2\mathrm{/}3})$. For comparison, it is known to be NP-hard to approximate (offline) graph coloring within a factor of $n^{1-\epsilon }$ for all fixed $\epsilon >0$. Therefore, our exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.