Skip to content
DraconiticResearch
Search Sources API
197,787 studies31 sourcesUpdated 35 min ago
PreprintCC BY 4.0arXiv

Acyclic Dichromatic Number of Tournaments: these are the Champions

  • Pierre Aboulker
  • Pierre Charbit
  • Samuel Coulomb
  • Kathryn Nurse
  • Lucas Picasarri-Arrieta
Open at sourcePDFDOICite

Abstract

The acyclic dichromatic number of an oriented graph is the minimum size of a vertex-partition such that the digraphs induced by any single part are acyclic, and the oriented bipartite graphs between any two parts are acyclic too. We characterize the subtournaments that must appear in every tournament with sufficiently large acyclic dichromatic number, thereby confirming a conjecture of Bang-Jensen, Picasarri-Arrieta, and Yeo and prove that acyclic dichromatic number satisfies a local to global property.

Related

  1. Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number
    Pierre Charbit, Samuel Coulomb
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Fractional Dichromatic Number and Domination in Tournaments
    Paul Colinot, Alantha Newman
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Cayley Tournaments Simultaneously Critical for the Clique and Dichromatic Numbers
    Guantao Chen, Shengze Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Acyclic Dicolourings of Oriented Graphs: Paths, Random Tournaments, and Critical Orders
    Yihang Liu, Zhenyu Yang, Yuwan Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Every tournament of dichromatic number 10 k2 has a vertex whose out-neighborhood has dichromatic number more than k
    Seokbeom Kim, Sang-il Oum
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{aboulker2026acyclic,
  title = {{Acyclic Dichromatic Number of Tournaments: these are the Champions}},
  author = {Pierre Aboulker and Pierre Charbit and Samuel Coulomb and Kathryn Nurse and Lucas Picasarri-Arrieta},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2607.14694},
  eprint = {2607.14694},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.14694},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Acyclic Dichromatic Number of Tournaments: these are the Champions
AU  - Pierre Aboulker
AU  - Pierre Charbit
AU  - Samuel Coulomb
AU  - Kathryn Nurse
AU  - Lucas Picasarri-Arrieta
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2607.14694
UR  - https://arxiv.org/abs/2607.14694
AB  - The acyclic dichromatic number of an oriented graph is the minimum size of a vertex-partition such that the digraphs induced by any single part are acyclic, and the oriented bipartite graphs between any two parts are acyclic too. We characterize the subtournaments that must appear in every tournament with sufficiently large acyclic dichromatic number, thereby confirming a conjecture of Bang-Jensen, Picasarri-Arrieta, and Yeo and prove that acyclic dichromatic number satisfies a local to global property.
ER  -