On the dichromatic number of surfaces
share
In this paper, we give bounds on the dichromatic number χ⃗(Σ) of a surface Σ, which is the maximum dichromatic number of an oriented graph embeddable on Σ. We determine the asymptotic behaviour of χ⃗(Σ) by showing that there exist constants a_1 and a_2 such that, a_1√(-c)/log(-c)≤χ⃗(Σ) ≤ a_2 √(-c)/log(-c) for every surface Σ with Euler characteristic c≤ -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 ℕ_1, the Klein bottle ℕ_2, the torus 𝕊_1, and Dyck's surface ℕ_3 are all equal to 3, and that the dichromatic numbers of the 5-torus 𝕊_5 and the 10-cross surface ℕ_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).
READ FULL TEXT