  Let $G$ be a graph with $n$ vertices, $m$ edges, average degree $\delta$, and
maximum degree $\Delta$. The "oriented chromatic number" of $G$ is the maximum,
taken over all orientations of $G$, of the minimum number of colours in a
proper vertex colouring such that between every pair of colour classes all
edges have the same orientation. We investigate the oriented chromatic number
of graphs, such as the hypercube, for which $\delta\geq\log n$. We prove that
every such graph has oriented chromatic number at least $\Omega(\sqrt{n})$. In
the case that $\delta\geq(2+\epsilon)\log n$, this lower bound is improved to
$\Omega(\sqrt{m})$. Through a simple connection with harmonious colourings, we
prove a general upper bound of $O(\Delta\sqrt{n})$ on the oriented chromatic
number. Moreover this bound is best possible for certain graphs. These lower
and upper bounds are particularly close when $G$ is ($c\log n$)-regular for
some constant $c>2$, in which case the oriented chromatic number is between
$\Omega(\sqrt{n\log n})$ and $O(\sqrt{n}\log n)$.

Combinatorics