On the dichromatic number of surfaces (Q2121762)

In this article, an oriented graph \(\vec{G}\) is a digraph whose underlying undirected graph is simple. In particular, the length of the shortest cycle in \(\vec{G}\) is at least 3. The dichromatic number \(\vec{\chi}(\vec{G})\) of an oriented graph \(\vec{G}\) is the smallest number of colors needed for vertex color \(\vec{G}\) in such a way that each color class of vertices induces no directed cycles, that is, each color class induces an acyclic subdigraph of \(\vec{G}\). Each surface \(\Sigma\) considered in this article is a compact (i.e.~closed and bounded) two-dimensional manifold and is therefore, by the classification theorem of surfaces, homeomorphic to the \(k\)-torus \({\mathbb{S}}_k\) (i.e.~a sphere with \(k\) handles) or the \(k\)-cross surface \({\mathbb{N}}_k\) (i.e.~a sphere with \(k\) cross-caps) for some non-negative integer \(k\). The dichromatic number \(\vec{\chi}(\Sigma)\) of a surface \(\Sigma\) is the least integer \(k\) such that every oriented graph embeddable in \(\Sigma\) has dichromatic number at most \(k\). This article studies three topics: (i) The asymptotic behavior of \(\vec{\chi}(\Sigma)\) when the Euler characteristic \(c(\Sigma)\) of the surface \(\Sigma\) tends to \(-\infty\). It is shown that there are real constants \(a_1\) and \(a_2\) such that \(a_1\frac{\sqrt{-c}}{\log(-c)} \leq \vec{\chi}(\Sigma)\leq a_2\frac{\sqrt{-c}}{\log(-c)}\) for every surface \(\Sigma\) with Euler characteristic \(c\leq -2\). (ii) Some explicit bounds for \(\vec{\chi}(\Sigma)\) for higher Euler characteristics are derived. It is shown that for projective plane, the Klein bottle, the torus, and the Dyck's surface, that is to say \(\Sigma = {\mathbb{N}}_1,{\mathbb{N}}_2,{\mathbb{S}}_1,{\mathbb{N}}_3\) respectively, one has \(\vec{\chi}(\Sigma) = 3\). Further it is shown that for \(\Sigma = {\mathbb{S}}_k\) for \(k = 2,3,4\) or for \(\Sigma = {\mathbb{N}}_k\) for \(k = 4,5,6,7,8,9\) one has \(3\leq \vec{\chi}(\Sigma)\leq 4\) and \(\vec{\chi}(\Sigma) = 4\) for \(\Sigma = {\mathbb{S}}_5, {\mathbb{N}}_{10}\). (iii) Finally, the complexity of determining if a digraph or oriented graph embeddable on a given surface is \(k\)-dicolorable is studied. In particular, it is shown that for any given surface, deciding whether a digraph embeddable on this surface is 2-dicolorable is NP-complete and that deciding whether a planar oriented graph is 2-dicolorable is NP-complete unless all planar oriented graphs are 2-dicolorable, something that was conjectured by \textit{V. Neumann-Lara} [J. Comb. Theory, Ser. B 33, 265--270 (1982; Zbl 0506.05031)].