The oriented chromatic number of random graphs of bounded degree

Abstract

The chromatic number of the random graph $\mathcal{G}(n,p)$ has long been studied and has inspired several landmark results. In the case where $p=d/n$, Achlioptas and Naor showed the chromatic number is asymptotically concentrated at $k_d$ or $k_d+1$, where $k_d$ is the smallest integer such that $d<2k_d\log k_d$. Kemkes et al. later proved the same result holds for $\mathcal{G}(n,d)$, the random $d$-regular graph. We consider the oriented chromatic number of the directed models $\vec{\mathcal{G}}(n,p)$ and $\vec{\mathcal{G}}(n,d)$, improving the best known upper bound from $O(d^2{2}^d)$ to $O({\sqrt{e}}^d)$.

Incorporated referee suggestions