χ⃗-binding tournaments with forest backedge graphs

Conjecture 4.3 (Gyárfás-Sumner for Tournaments) · arXiv:2310.04265

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

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

Status disproved high confidence

Disproved by Aubian (Theorem 4.2, arXiv:2401.07776). Having an ordering whose backedge graph is a forest does not suffice for a tournament to be χ⃗-binding. The necessary ('only if') direction established in the source paper is unaffected.

Cited literature (1)

counterexample Computing the clique number of tournaments (2024)

Guillaume Aubian · arXiv preprint · arXiv:2401.07776

Theorem 4.2 disproves the forest-backedge sufficiency assertion, restated as Conjecture 4.1 there: for some forest-orderable H, H-free tournaments have bounded clique number but unbounded dichromatic number.

Reviewer notes. Corrected on 2026-09-10 following Samuel Coulomb's report; Section 4 of arXiv:2401.07776 was checked in the full text. The relevant result is the structural counterexample in Theorem 4.2, not the paper's separate NP-completeness theorem.

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

Conjecture. A tournament $H$ is $\operatorname{\overrightarrow{\chi}}$-binding if and only if $H$ has a backedge graph which is a forest.

Context

The authors propose this as the directed analogue of the celebrated Gyárfás-Sumner Conjecture, where a tournament $H$ is $\operatorname{\overrightarrow{\chi}}$-binding if the class of tournaments not containing $H$ as a subtournament is $\operatorname{\overrightarrow{\chi}}$-bounded. The 'only if' direction is proved as Theorem 4.4, and it is shown that it suffices to prove the 'if' direction for trees.

Source paper

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