PreprintCC BY 4.0arXiv
Bounded Twin-Width Tournaments are dchi-Bounded
Abstract
For a tournament T and a vertex ordering ≺, let T≺ be the graph of backward arcs in ≺. The diclique number of a tournament is domega(T)=min≺ω(T≺), and the dichromatic number is dchi(T)=min≺χ(T≺). We prove a mixed parameter transfer theorem: for all k and r, if tww(T)≤ k and ω(T≺)≤ r, then the ordered twin-width of (T≺,≺) is bounded by a function of k and r. The proof combines the regular-semigrid theorem for ordered graphs with permutation-encoding obstructions to bounded twin-width in tournaments. Together with polynomial χ-boundedness of graphs of bounded twin-width, this implies that tournaments of bounded twin-width are dchi-bounded by domega, resolving a conjecture of Aboulker, Aubian, Charbit, and Lopes.
Related
- Monadically Dependent Graph Classes Have Almost Bounded Merge-Width
- Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width
- Inverting Dependently Random Tournaments
- A New Upper Bound for 7-Universal Tournaments
- Random Tournaments Are Asymptotically Almost Surely Link-irregular
BibTeX
@misc{tang2026bounded,
title = {{Bounded Twin-Width Tournaments are $\dchi$-Bounded}},
author = {Chaoliang Tang and Junchi Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02763},
eprint = {2609.02763},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02763},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bounded Twin-Width Tournaments are dchi-Bounded
AU - Chaoliang Tang
AU - Junchi Zhang
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.02763
UR - https://arxiv.org/abs/2609.02763
AB - For a tournament T and a vertex ordering ≺, let T^≺ be the graph of backward arcs in ≺. The diclique number of a tournament is domega(T)=min_≺ω(T^≺), and the dichromatic number is dchi(T)=min_≺χ(T^≺). We prove a mixed parameter transfer theorem: for all k and r, if tww(T)≤ k and ω(T^≺)≤ r, then the ordered twin-width of (T^≺,≺) is bounded by a function of k and r. The proof combines the regular-semigrid theorem for ordered graphs with permutation-encoding obstructions to bounded twin-width in tournaments. Together with polynomial χ-boundedness of graphs of bounded twin-width, this implies that tournaments of bounded twin-width are dchi-bounded by domega, resolving a conjecture of Aboulker, Aubian, Charbit, and Lopes.
ER -