Oriented Colouring Graphs of Bounded Degree and Degeneracy

Abstract: This paper considers upper bounds on the oriented chromatic number,

c h i_{o}

, of graphs in terms of their maximum degree

D e l t a

and/or their degeneracy

d

. In particular we show that asymptotically,

c h i_{o} l e q c h i_{2} f (d) 2^{d}

where

f (d) g e q (f r a c 1 l o g_{2} (e) - 1 + e p s i l o n) d^{2}

and

c h i_{2} l e q 2^{f r a c f (d) d}

. This improves a result of MacGillivray, Raspaud, and Swartz of the form

c h i_{o} l e q 2^{c h i_{2}} - 1

. The rest of the paper is devoted to improving prior bounds for

c h i_{o}

in terms of

D e l t a

and

d

by refining the asymptotic arguments involved.

This page was built for publication: Oriented Colouring Graphs of Bounded Degree and Degeneracy