χ̄-boundedness for bounded twin-width tournaments

Conjecture 3.12 · arXiv:2310.04265

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

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

Status solved high confidence

Proved by Aubian and Coulomb (Theorem 5.7, arXiv:2609.07481) and by Tang and Zhang (Corollary 1.2, arXiv:2609.02763). For each fixed twin-width bound k, the dichromatic number of a tournament is bounded by a function of its tournament clique number.

Cited literature (2)

proof Clique Number of Tournaments II (2026)

Guillaume Aubian, Samuel Coulomb · arXiv preprint · arXiv:2609.07481

Theorem 5.7 proves that classes of tournaments with bounded twin-width are χ⃗-bounded.
proof Bounded Twin-Width Tournaments are χ⃗-Bounded (2026)

Chaoliang Tang, Junchi Zhang · arXiv preprint · arXiv:2609.02763

Corollary 1.2 gives, for every k ≥ 0, a function f_k bounding the dichromatic number by f_k of the tournament clique number whenever twin-width is at most k.

Reviewer notes. Corrected on 2026-09-10 following Samuel Coulomb's report; both cited results were checked in the full text. Tang and Zhang call the source conjecture 3.13, but its statement matches this catalog's original Conjecture 3.12. The result is χ⃗-boundedness, not a constant bound on dichromatic number or a claim of polynomial χ⃗-boundedness.

Auto-reviewed 2026-09-10 with codex (web search enabled).

Conjecture. Let $k\geq 1$. The class of tournaments with twin-width at most $k$ is $\operatorname{\overrightarrow{\chi}}$-bounded.

Context

For every integer $k\geq 2$, the tournament $S_k$ has twin-width $1$ and dichromatic number $k$, so tournaments with bounded twin-width can have arbitrarily large dichromatic number. Nevertheless, the authors conjecture that $\operatorname{\overrightarrow{\chi}}$-boundedness holds. Conjecture 3.13 is presented as a sufficient condition implying this conjecture.

Source paper

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