On the dichromatic number of surfaces

Description

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 N 1 , the Klein bottle N 2 , the torus S 1 , and Dyck's surface N 3 are all equal to 3, and that the dichromatic numbers of the 5-torus S 5 and the 10-cross surface 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).

Abstract

International audience

Additional details