Skip to content
DraconiticResearch
Search Sources API
181,716 studies31 sourcesUpdated 38 min ago
PreprintCC BY 4.0arXiv

Fractional Dichromatic Number and Domination in Tournaments

  • Paul Colinot
  • Alantha Newman
Open at sourcePDFDOICite

Abstract

Bourneuf, Charbit and Thomassé [BCT25] showed that the domination number of a tournament can be bounded as a function of its fractional dichromatic number. The function proved was exponential and the tools were based on VC-dimension. In this paper, we present two new proofs of this theorem. The first proof is based on a reduction to the problem of bounding the domination number of a (1/2−ε)-majority tournament, for which [BCT25] and Charikar, Ramakrishnan and Wang [CRW26] gave tight bounds. This proof yields the same exponential bound on the domination number as in [BCT25]. The second proof gives a quasilinear bound for the domination in terms of the fractional dichromatic number. It was obtained via AI and was inspired by the recent book proof of the existence of a Condorcet Winning Set of size five due to Ramakrishnan [Ram26].

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. Acyclic Dichromatic Number of Tournaments: these are the Champions
    Pierre Aboulker, Pierre Charbit, Samuel Coulomb +2
    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. 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
  5. The maximum number of Hamiltonian cycles in tournaments
    Alexander Divoux, Shouda Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{colinot2026fractional,
  title = {{Fractional Dichromatic Number and Domination in Tournaments}},
  author = {Paul Colinot and Alantha Newman},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.35186},
  eprint = {2609.35186},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.35186},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Fractional Dichromatic Number and Domination in Tournaments
AU  - Paul Colinot
AU  - Alantha Newman
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.35186
UR  - https://arxiv.org/abs/2609.35186
AB  - Bourneuf, Charbit and Thomassé [BCT25] showed that the domination number of a tournament can be bounded as a function of its fractional dichromatic number. The function proved was exponential and the tools were based on VC-dimension. In this paper, we present two new proofs of this theorem. The first proof is based on a reduction to the problem of bounding the domination number of a (1/2−ε)-majority tournament, for which [BCT25] and Charikar, Ramakrishnan and Wang [CRW26] gave tight bounds. This proof yields the same exponential bound on the domination number as in [BCT25]. The second proof gives a quasilinear bound for the domination in terms of the fractional dichromatic number. It was obtained via AI and was inspired by the recent book proof of the existence of a Condorcet Winning Set of size five due to Ramakrishnan [Ram26].
ER  -