{"id":"arxiv/2609.22931","url":"https://arxiv.org/abs/2609.22931","tags":["math.CO"],"score":0,"title":"Acyclic Dicolourings of Oriented Graphs: Paths, Random Tournaments, and Critical Orders","domain":"math.CO","source":"arxiv","authors":["Yihang Liu","Zhenyu Yang","Yuwan Zhang"],"reviews":0,"subject":"math.CO","summary":"An acyclic dicolouring of an oriented graph is a vertex partition in which every colour class and every bipartite subdigraph induced by two classes is acyclic. We first prove the Gallai--Roy-type bound $\\vecχ_a(D)\\leq L(D)$, where $L(D)$ is the maximum order of a directed path. Let $r=\\log_2(8/7)$. Bang-Jensen, Picasarri-Arrieta, and Yeo previously constructed tournaments of order $n$ whose acyclic dichromatic number is at least $n-(\\frac8r)\\log_2 n-\\log_2\\log_2 n$. We improve the leading logarithmic coefficient by a factor of two: for the uniform random tournament $\\mathcal{T}_n$,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-19","reactions":{}}