The Oriented Chromatic Number of Random Graphs of Bounded Degree

Abstract

ABSTRACT The chromatic number of the random graph has long been studied and has inspired several landmark results. In the case where , Achlioptas and Naor showed the chromatic number is asymptotically two‐point concentrated. Kemkes et al. later proved that the same result holds for , the random ‐regular graph. We consider the oriented chromatic number of the directed models and . Previous extremal results can be used to bound the oriented chromatic number of a random ‐regular digraph between and . Using colorings by doubly regular tournaments, we improve the upper bound to . As part of our proof, we extend an optimization result of Achlioptas and Naor for functions over doubly stochastic matrices, which may be of independent interest.