→χ-bounding ordering for bounded-twin-width tournaments

Conjecture 3.13 · arXiv:2310.04265

arXiv Conjecture high confidence— first stated 2023-10-06

Authors: Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes

Status unclear low confidence

Conjecture 3.13 asks for a function $f$ such that every tournament $T$ has one ordering $\prec^*$ satisfying both $\omega(T^{\prec^*})\leq f(\operatorname{\overrightarrow{\omega}}(T))$ and $\operatorname{tww}(T,\prec^*)\leq f(\operatorname{tww}(T))$. It implies Conjecture 3.12. The status remains unclear because the May 2026 review could not identify which conjecture a related 2024 counterexample targets.

Cited literature (2)

partial Computing the clique number of tournaments (2024)

unverified · arXiv preprint · arXiv:2401.07776

Proves that deciding whether a tournament has clique number at most k is NP-complete, and provides a counterexample to some conjecture of Aboulker, Aubian, Charbit, and Lopes from arXiv:2310.04265; which specific conjecture (possibly 3.12 or another) could not be confirmed from the abstract.
partial Characterizing Large Clique Number in Tournaments (2025)

unverified · arXiv preprint · arXiv:2602.09863

Shows that large clique number in tournaments is always certified by a bounded-size subtournament from one of two simple families; does not appear to directly address the ordering conjecture (Conjecture 3.13).

Reviewer notes. The complete two-part statement was verified in the cached arXiv HTML. Full-text verification of arXiv:2401.07776 is still needed to settle the status.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. There exists a function $f$ such that for every tournament $T$, there exists an ordering $\prec^{*}$ of $V(T)$ such that $\omega(T^{\prec^{*}})\leq f(\operatorname{\overrightarrow{\omega}}(T))$ and $\operatorname{tww}(T,\prec^{*})\leq f(\operatorname{tww}(T))$.

Context

This conjecture is introduced as a strengthening implying Conjecture 3.12 on $\operatorname{\overrightarrow{\chi}}$-boundedness of bounded-twin-width tournaments. It concerns the existence of a single ordering simultaneously witnessing relevant structural and coloring properties.

Source paper

Clique number of tournaments
Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes · 2023-10-06
https://arxiv.org/abs/2310.04265