{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T04:27:41Z","timestamp":1772684861602,"version":"3.50.1"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>In this paper, we give bounds on the dichromatic number\u00a0 $\\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)} \u00a0 \\leq \\vec{\\chi}(\\Sigma) \\leq\u00a0 a_2\u00a0 \\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 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).<\/jats:p>","DOI":"10.37236\/10223","type":"journal-article","created":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T12:19:59Z","timestamp":1645705199000},"source":"Crossref","is-referenced-by-count":1,"title":["On the Dichromatic Number of Surfaces"],"prefix":"10.37236","volume":"29","author":[{"given":"Pierre","family":"Aboulker","sequence":"first","affiliation":[]},{"given":"Fr\u00e9d\u00e9ric","family":"Havet","sequence":"additional","affiliation":[]},{"given":"Kolja","family":"Knauer","sequence":"additional","affiliation":[]},{"given":"Cl\u00e9ment","family":"Rambaud","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2022,2,11]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i1p30\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i1p30\/code","content-type":"application\/zip","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i1p30\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T12:19:59Z","timestamp":1645705199000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v29i1p30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,11]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1,27]]}},"URL":"https:\/\/doi.org\/10.37236\/10223","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,11]]},"article-number":"P1.30"}}