Local clique number bounds global in tournaments

Conjecture 5.6 · 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

Conjecture 5.6 asks whether bounded out-neighborhood clique number implies bounded global clique number in tournaments, as a clique-number analogue of the Harutyunyan-Le-Thomassé-Wu theorem. A 2024 follow-up paper by Aubian (arXiv:2401.07776) explicitly disproves a conjecture of Aboulker-Aubian-Charbit-Lopes from arXiv:2310.04265, but full-text access was required to determine whether it targets Conjecture 5.6 specifically or another conjecture in the same paper (e.g., Conjecture 5.3, which implies 5.6 per Theorem 5.7). The status of Conjecture 5.6 therefore cannot be settled with certainty from the available abstract-level evidence.

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 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 Conjecture 5.6 is the one disproved.

Reviewer notes. arXiv:2401.07776 (Aubian, Jan 2024) is the most relevant follow-up: its abstract states it gives a counterexample to a conjecture of the source-paper authors, but does not name the conjecture. Since Theorem 5.7 of the source paper establishes that Conjecture 5.3 implies Conjecture 5.6, a counterexample to 5.3 would not settle 5.6. Full-text reading of 2401.07776 is needed to resolve this. A second 2026 paper (arXiv:2602.08736, Aubian-Kuffner) disproves a different conjecture about dichromatic number and is unrelated to Conjecture 5.6.

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

Conjecture. There exists a function $g$ such that, for every integer $t$, if $T$ is a tournament such that for every $v\in V(T)$, $\operatorname{\overrightarrow{\omega}}(N^{+}(v))\leq t$, then $\operatorname{\overrightarrow{\omega}}(T)\leq g(t)$.

Context

This is the clique-number analogue of Theorem 4.8 (Harutyunyan-Le-Thomassé-Wu), which asserts that bounded local dichromatic number implies bounded global dichromatic number. Theorem 5.7 shows that Conjecture 5.3 implies Conjecture 5.6.

Source paper

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