In this paper, we give bounds on the dichromatic number $vec{chi}(Sigma)$ of a surface $Sigma$, which is the maximum dichromatic number of an oriented graph embeddable on $Sigma$. We determine the asymptotic behaviour of $vec{chi}(Sigma)$ by showing that there exist constants $a_1$ and $a_2$ such that, $ a_1frac{sqrt{-c}}{log(-c)} leq vec{chi}(Sigma) leq a_2 frac{sqrt{-c}}{log(-c)} $ for every surface $Sigma$ with Euler characteristic $cleq -2$. We then give more explicit bounds for some surfaces with high Euler characteristic. In particular, we show that the dichromatic numbers of the projective plane $mathbb{N}_1$, the Klein bottle $mathbb{N}_2$, the torus $mathbb{S}_1$, and Dycks surface $mathbb{N}_3$ are all equal to $3$, and that the dichromatic numbers of the $5$-torus $mathbb{S}_5$ and the $10$-cross surface $mathbb{N}_{10}$ are equal to $4$. We also consider the complexity of deciding whether a given digraph or oriented graph embedabble in a fixed surface is $k$-dicolourable. In particular, we show that for any surface, deciding whether a digraph embeddable on this surface is $2$-dicolourable is NP-complete, and that deciding whether a planar oriented graph is $2$-dicolourable is NP-complete unless all planar oriented graphs are $2$-dicolourable (which was conjectured by Neumann-Lara).
تحميل البحث