On Oriented Colourings of Graphs on Surfaces

Abstract

For an oriented graph $G$, the least number of colours required to oriented colour $G$ is called the oriented chromatic number of $G$ and denoted ${\chi }_o(G)$.For a non-negative integer $g$ let ${\chi }_o(g)$ be the least integer such that ${\chi }_o(G)\le {\chi }_o(g)$ for every oriented graph $G$ with Euler genus at most $g$. We will prove that ${\chi }_o(g)$ is nearly linear in the sense that $\Omega (\frac{g}{\log (g)})\le {\chi }_o(g)\le O(g\log (g))$. This resolves a question of the author, Bradshaw, and Xu, by improving their bounds of the form $\Omega ((\frac{g^2}{\log (g)}{)}^{1/3})\le {\chi }_o(g)$ and ${\chi }_o(g)\le O(g^{6400})$.

arXiv comment14 pages, 2 figures