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 solved high confidence

Proved unconditionally by Chen and Wang (Theorem 1.1, arXiv:2609.08658), who construct infinitely many pairwise nonisomorphic k-ω⃗-critical tournaments for every k ≥ 3.

Cited literature (1)

proof Cayley Tournaments Simultaneously Critical for the Clique and Dichromatic Numbers (2026)

Guantao Chen, Shengze Wang · arXiv preprint · arXiv:2609.08658

Theorem 1.1 constructs such tournaments at unbounded orders, simultaneously critical for the clique and dichromatic numbers.

Reviewer notes. Corrected on 2026-09-10 following Samuel Coulomb's report; Theorem 1.1 was checked in the full text. The constructive result covers every k ≥ 3 without a complexity assumption. NP-completeness alone is not an unconditional proof: a finite-obstruction argument would require P ≠ NP.

Auto-reviewed 2026-09-10 with codex (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