Acyclic Dicolourings of Oriented Graphs: Paths, Random Tournaments, and Critical Orders
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$,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.22931
curl -X POST /api/v1/records/arxiv/2609.22931/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.22931/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'