Skip to content
DraconiticResearch
Search Sources API
182,549 studies31 sourcesUpdated 56 min ago
PreprintCC BY 4.0arXiv

Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number

  • Pierre Charbit
  • Samuel Coulomb
Open at sourcePDFDOICite

Abstract

In the 1960s, Erdős and Hajnal conjectured that every graph with sufficiently large chromatic number contains a subgraph of large girth (size of a smallest cycle) and large chromatic number. In this paper, we prove that every tournament with sufficiently large dichromatic number contains a subdigraph of large digirth (size of a smallest directed cycle) and large dichromatic number. We investigate the same statement when replacing digirth by girth (of the underlying graph). We show that it implies the conjecture of Erdős and Hajnal, and prove it for a particular family of tournaments.

Related

  1. Acyclic Dichromatic Number of Tournaments: these are the Champions
    Pierre Aboulker, Pierre Charbit, Samuel Coulomb +2
    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. 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{charbit2026digraphs,
  title = {{Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number}},
  author = {Pierre Charbit and Samuel Coulomb},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.21895},
  eprint = {2609.21895},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.21895},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number
AU  - Pierre Charbit
AU  - Samuel Coulomb
PY  - 2026
DA  - 2026/09/18
PB  - arXiv
DO  - 10.48550/arxiv.2609.21895
UR  - https://arxiv.org/abs/2609.21895
AB  - In the 1960s, Erdős and Hajnal conjectured that every graph with sufficiently large chromatic number contains a subgraph of large girth (size of a smallest cycle) and large chromatic number. In this paper, we prove that every tournament with sufficiently large dichromatic number contains a subdigraph of large digirth (size of a smallest directed cycle) and large dichromatic number. We investigate the same statement when replacing digirth by girth (of the underlying graph). We show that it implies the conjecture of Erdős and Hajnal, and prove it for a particular family of tournaments.
ER  -