Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 57 min ago
PreprintarXiv licencearXiv

Acyclic Dicolourings of Oriented Graphs: Paths, Random Tournaments, and Critical Orders

  • Yihang Liu
  • Zhenyu Yang
  • Yuwan Zhang
Open at sourcePDFDOICite

Abstract

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 χ⃗a(D)≤ L(D), where L(D) is the maximum order of a directed path. Let r=log2(8/7). Bang-Jensen, Picasarri-Arrieta, and Yeo previously constructed tournaments of order n whose acyclic dichromatic number is at least n−(8/r)log2 n−log2log2 n. We improve the leading logarithmic coefficient by a factor of two: for the uniform random tournament 𝒯n, asymptotically almost surely, χ⃗a(𝒯n)≥ n−4/rlog2 n+2/rlog2log2 n−O(1). Finally, if m(k) denotes the minimum order of an oriented graph with acyclic dichromatic number at least k, tournament completion shows that the same minimum is obtained over tournaments. We prove m(3)=5 and m(4)=7 and classify the tournament witnesses at these minimum orders: there is one at order five and two at order seven.

Related

  1. Intersections of Oriented Graphs and Tournaments
    Zhanping Yang, Qinghou Zeng
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Acyclic Dichromatic Number of Tournaments: these are the Champions
    Pierre Aboulker, Pierre Charbit, Samuel Coulomb +2
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Hamiltonicity of graphs of acyclic orientations and acyclic polynomials
    Leonie Mühlherr, Germain Poullot
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Cayley Tournaments Simultaneously Critical for the Clique and Dichromatic Numbers
    Guantao Chen, Shengze Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Causal Discovery beyond Conditional Independence: Identifiability, Algorithms, and Statistical Inference for Directed Acyclic and Cyclic Graphs
    Yang Ni
    arXivPreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{liu2026acyclic,
  title = {{Acyclic Dicolourings of Oriented Graphs: Paths, Random Tournaments, and Critical Orders}},
  author = {Yihang Liu and Zhenyu Yang and Yuwan Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.22931},
  eprint = {2609.22931},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.22931},
}
RIS
TY  - UNPB
TI  - Acyclic Dicolourings of Oriented Graphs: Paths, Random Tournaments, and Critical Orders
AU  - Yihang Liu
AU  - Zhenyu Yang
AU  - Yuwan Zhang
PY  - 2026
DA  - 2026/09/19
PB  - arXiv
DO  - 10.48550/arxiv.2609.22931
UR  - https://arxiv.org/abs/2609.22931
AB  - 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 χ⃗_a(D)≤ 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−(8/r)log_2 n−log_2log_2 n. We improve the leading logarithmic coefficient by a factor of two: for the uniform random tournament 𝒯_n, asymptotically almost surely, χ⃗_a(𝒯_n)≥ n−4/rlog_2 n+2/rlog_2log_2 n−O(1). Finally, if m(k) denotes the minimum order of an oriented graph with acyclic dichromatic number at least k, tournament completion shows that the same minimum is obtained over tournaments. We prove m(3)=5 and m(4)=7 and classify the tournament witnesses at these minimum orders: there is one at order five and two at order seven.
ER  -