→χ-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 from arXiv:2310.04265 asserts the existence of a function f such that every tournament T admits a single vertex ordering simultaneously witnessing structural and coloring properties, and is described as a strengthening that implies Conjecture 3.12 on the chi-arrow-boundedness of bounded-twin-width tournaments. A January 2024 follow-up paper (arXiv:2401.07776) proves NP-completeness of computing the clique number of tournaments and provides a counterexample to some conjecture of the same authors, but the full text could not be retrieved to confirm whether Conjecture 3.13 is specifically targeted. Since Conjecture 3.13 logically implies Conjecture 3.12, a refutation of 3.12 would also refute 3.13, leaving the status unclear pending full-text verification.

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 paper arXiv:2401.07776 explicitly constructs a counterexample to 'a conjecture' of Aboulker et al. in arXiv:2310.04265, but the HTML version returned 404 and the PDF was unreadable binary, so it was not possible to confirm this is Conjecture 3.13 rather than 3.12 or another. Since Conjecture 3.13 implies Conjecture 3.12 (by the paper's own framing), a counterexample to 3.12 would also render 3.13 vacuously false as a standalone statement. Full-text access to arXiv:2401.07776 is required to resolve the status definitively.

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:

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.

Notes. Statement appears truncated in the source; conditions following 'such that:' are not captured in the extracted text.

Source paper

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