On the dichromatic number of surfaces

Abstract

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_1\frac{\sqrt{-c}}{\log (-c)}\le \vec{\chi }(\Sigma )\le a_2\frac{\sqrt{-c}}{\log (-c)}$ for every surface $\Sigma$ with Euler characteristic $c\le -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 Dyck's 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 embeddable on a fixed surface is $k$-dicolourable. In particular, we show that for any fixed 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).

26 pages, 5 figures, improved asymptotic bounds