The oriented chromatic number of random graphs of bounded degree

Publication date 24 February 2022

Abstract: The chromatic number of the random graph

m a t h c a l 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 < 2 k_{d} l o g k_{d}

. Kemkes et al. later proved the same result holds for

m a t h c a l G (n, d)

, the random

d

-regular graph. We consider the oriented chromatic number of the directed models

v e c m a t h c a l G (n, p)

and

v e c m a t h c a l G (n, d)

, improving the best known upper bound from

O (d^{2} 2^{d})

to

O (s q r t e^{d})

.

This page was built for publication: The oriented chromatic number of random graphs of bounded degree