Simultaneous ω-ordering and χ-ordering in tournaments

Question 3.5 · arXiv:2310.04265

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

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

Status unclear medium confidence

A follow-up paper arXiv:2401.07776 (Aubian, 2024) titled 'Computing the clique number of tournaments' explicitly provides a counterexample to a conjecture of Aboulker, Aubian, Charbit and Lopes, but its abstract does not specify which conjecture from the source paper is disproved. It is unconfirmed whether this counterexample addresses Question 3.5 (existence of a simultaneous omega-ordering and chi-ordering for every tournament) or a different conjecture from the same paper. No other follow-up directly addressing Question 3.5 was found.

Cited literature (1)

counterexample Computing the clique number of tournaments (2024)

Guillaume Aubian · arXiv preprint · arXiv:2401.07776

Proves NP-completeness of deciding whether a tournament has clique number at most k (for k >= 3), and modifies the construction to provide a counterexample to a conjecture of Aboulker, Aubian, Charbit and Lopes; it is unconfirmed whether Question 3.5 is the specific conjecture disproved.

Reviewer notes. arXiv:2401.07776 (Aubian 2024) reports a counterexample to a conjecture from arXiv:2310.04265 but does not name it in the abstract; full-text access would be required to confirm whether Question 3.5 specifically is the conjecture disproved. Question 3.5 concerns simultaneous existence of omega-orderings and chi-orderings, a structural existence question, whereas 2401.07776 is primarily focused on computational complexity of the clique number — so the counterexample may concern a different conjecture in the source paper.

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

Question. Is it true that for every tournament $T$, there exists $\prec\in\mathfrak{S}(T)$ such that $\prec$ is both a $\operatorname{\overrightarrow{\omega}}$-ordering and a $\operatorname{\overrightarrow{\chi}}$-ordering?

Context

The paper establishes that for any $\operatorname{\overrightarrow{\omega}}$-ordering $\prec$ of a tournament $T$, one has $\operatorname{\overrightarrow{\chi}}(T)\leq\chi(T^{\prec})\leq\operatorname{\overrightarrow{\chi}}(T)^{2}$. The question asks whether a single ordering can simultaneously witness both the clique number and the dichromatic number.

Source paper

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