Skip to Main content Skip to Navigation
New interface
Book sections

On the dichromatic number of surfaces

Pierre Aboulker 1 Frédéric Havet 2 Kolja Knauer 3 Clément Rambaud 1 
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Document type :
Book sections
Complete list of metadata

https://hal.inria.fr/hal-03424140
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Wednesday, November 10, 2021 - 12:43:38 PM
Last modification on : Thursday, August 4, 2022 - 4:58:28 PM
Long-term archiving on: : Friday, February 11, 2022 - 6:47:15 PM

File

dichromatic-eurocomb.pdf
Files produced by the author(s)

Identifiers

Citation

Pierre Aboulker, Frédéric Havet, Kolja Knauer, Clément Rambaud. On the dichromatic number of surfaces. Extended Abstracts EuroComb 2021, 14, Springer International Publishing, pp.181-187, 2021, Trends in Mathematics, ⟨10.1007/978-3-030-83823-2_29⟩. ⟨hal-03424140⟩

Share

Metrics

Record views

79

Files downloads

126