χ⃗-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 open high confidence

The 'only if' direction of this biconditional conjecture was established in the source paper itself (Theorem 4.4), and the open 'if' direction was further reduced to the case of trees. No subsequent work proving the remaining implication has been found. A closely related follow-up by three of the four original authors (arXiv:2402.10782, revised January 2026) proves that deciding whether a tournament admits a forest-ordering — the right-hand-side structural condition — is NP-complete, indicating computational hardness around that condition but leaving the χ̄-binding implication open.

Cited literature (1)

partial Finding forest-orderings of tournaments is NP-complete (2024)

Pierre Aboulker, Guillaume Aubian, Raul Lopes · arXiv preprint · arXiv:2402.10782

Proves that deciding whether a tournament admits an ordering whose backedge graph is a forest (the right-hand-side condition of Conjecture 4.3) is NP-complete, and connects this to dichromatic number and Erdős-Hajnal properties, but does not resolve the χ̄-binding implication.

Reviewer notes. The conjecture as stated already has the 'only if' direction proved in the source paper (Theorem 4.4), so the genuinely open part is the 'if' direction, further reduced to trees. arXiv:2402.10782 establishes NP-completeness of detecting the forest-ordering condition but does not prove the χ̄-binding implication. The conjecture is the directed analogue of the undirected Gyárfás-Sumner conjecture, which is itself still open in general.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (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