Infinitely Many k-ω-critical Tournaments

Conjecture 5.10 · arXiv:2310.04265

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

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

Status unclear medium confidence

No follow-up paper specifically addressing Conjecture 5.10 (infinitely many k-\overrightarrow{\omega}-critical tournaments for k≥3) was found. A January 2024 paper (arXiv:2401.07776) on NP-completeness of computing the clique number of tournaments explicitly disproves a conjecture of Aboulker, Aubian, Charbit and Lopes from arXiv:2310.04265, but the abstract does not identify which conjecture; full-text verification was not possible within the web-call budget. A February 2026 paper (arXiv:2602.09863) characterises tournaments with large clique number but does not appear to address k-\overrightarrow{\omega}-criticality.

Cited literature (2)

partial Computing the clique number of tournaments (2024)

Unknown (to be verified) · 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 a conjecture of Aboulker, Aubian, Charbit and Lopes (arXiv:2310.04265); the abstract does not specify which conjecture, so it is unclear whether this resolves Conjecture 5.10.
partial Characterizing Large Clique Number in Tournaments (2026)

Unknown (to be verified) · arXiv preprint · arXiv:2602.09863

Characterises tournaments with large clique number via two families; related to the source paper's programme but does not appear to address k-\overrightarrow{\omega}-criticality or Conjecture 5.10 directly.

Reviewer notes. arXiv:2401.07776 explicitly states it disproves a conjecture of Aboulker, Aubian, Charbit and Lopes, but the abstract does not specify which one among the several conjectures in arXiv:2310.04265. Full-text access to 2401.07776 (HTML 404, PDF binary) was not achievable within the 5-call budget. Status is therefore 'unclear' rather than 'open' or 'disproved'.

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

Conjecture. For every integer $k\geq 3$, there is an infinite number of $k$-$\operatorname{\overrightarrow{\omega}}$-critical tournaments.

Context

A tournament $T$ is $k$-$\operatorname{\overrightarrow{\omega}}$-critical if $\operatorname{\overrightarrow{\omega}}(T)=k$ and $\operatorname{\overrightarrow{\omega}}(T-v)=k-1$ for every $v\in V(T)$. For $k=1,2$ there is exactly one such tournament; the conjecture asserts infinitely many exist for all $k\geq 3$. If true it answers Question 5.9 negatively; if false it answers it positively.

Source paper

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