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 a1 and a2 such that, a1 √ −c log(−c) ≤ − → χ (Σ) ≤ a2 √ −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 N1, the Klein bottle N2, the torus S1, and Dyck's surface N3 are all equal to 3, and that the dichromatic numbers of the 5-torus S5 and the 10-cross surface N10 are equal to 4.

Abstract

International audience

Additional details