Metraipolis › archive › dc_6b45a331d46f

Crossing tournaments are polynomially $\vecχ$-bounded — arXiv:2608.09710

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.09710
License (as archived)
CC0-1.0
Archived
2026-10-19T09:09:05.336Z
SHA-256 of the archived text
3cf8e64fb82f3e60495b8d357d439518857cd1f7e74b8e9c80343ae95b8856a3
Stable URL of this page
https://metraipolis.com/documento/dc_6b45a331d46f

How to cite

Crossing tournaments are polynomially $\vecχ$-bounded — arXiv:2608.09710 — arXiv (en), https://arxiv.org/abs/2608.09710 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6b45a331d46f (Metraipolis archive dc_6b45a331d46f, sha256 3cf8e64fb82f3e60495b8d357d439518857cd1f7e74b8e9c80343ae95b8856a3)
BibTeX
@misc{dc6b45a331d46f,
  title = {Crossing tournaments are polynomially $vecχ$-bounded — arXiv:2608.09710},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.09710},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6b45a331d46f; sha256 3cf8e64fb82f3e60495b8d357d439518857cd1f7e74b8e9c80343ae95b8856a3},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.09710. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Given a tournament $T$, Aboulker, Aubian, Charbit, and Lopes (2023) defined its clique number $\vec{\omega}(T)$ as the minimum clique number of a backedge graph of $T$, and raised the question: Which classes of tournaments are polynomially $\vec{\chi}$-bounded? Aboulker, Duron, Jacob, Kimbrough, Thomassé, and this work's authors (2026) showed that this holds for classes of tournaments whose arc sets may be written as the union of a bounded number of comparability digraphs. What about classes of tournaments that do not admit such a decomposition? The crossing tournaments of Nguyen, Scott, and Seymour (2025) are an example of such a class, as shown in the aforementioned 2026 work; we show that nonetheless crossing tournaments are polynomially $\vec{\chi}$-bounded by adapting a method of Davies and McCarty (2021) and Davies (2022). We additionally show that we cannot extend this result for crossing tournaments to tournaments with chordal graphs as backedge graphs.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2608.09710 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:05:33.590Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).