Skip to Main content Skip to Navigation
Reports

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 $\vec{\chi}(\Sigma)$ of a surface $\Sigma$, which is the maximum dichromatic number of an oriented graph embeddable on $\Sigma$. We determine the asymptotic behaviour of $\vec{\chi}(\Sigma)$ by showing that there exist 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$. 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 $\mathbb{N}_1$, the Klein bottle $\mathbb{N}_2$, the torus $\mathbb{S}_1$, and Dyck's surface $\mathbb{N}_3$ are all equal to $3$, and that the dichromatic numbers of the $5$-torus $\mathbb{S}_5$ and the $10$-cross surface $\mathbb{N}_{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).
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/hal-03269426
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Thursday, June 24, 2021 - 8:45:13 AM
Last modification on : Saturday, June 25, 2022 - 11:50:56 PM

Links full text

Identifiers

  • HAL Id : hal-03269426, version 1
  • ARXIV : 2102.01034

Citation

Pierre Aboulker, Frédéric Havet, Kolja Knauer, Clément Rambaud. On the dichromatic number of surfaces. [Research Report] Inria; CNRS; I3S; Université Côte D'Azur. 2021. ⟨hal-03269426⟩

Share

Metrics

Record views

32