Dominating number forcing in tournament subtournaments

Problem 4 · arXiv:1702.01607

arXiv Problem high confidence— first stated 2017-03-15

Authors: Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé, Hehui Wu

Status open high confidence

Problem 4 from Harutyunyan–Le–Thomassé–Wu (arXiv:1702.01607) asks whether sufficiently large dominating number forces a bounded-size subtournament of large dominating number. As of 2026, the conjecture remains open. Aboulker, Aubian, Charbit, and Lopes (arXiv:2310.04265, 2023) revisited this in their study of clique number of tournaments: their Section 5 ('Local to Global – Links with domination number') references the HLTW work, introduces an intermediate conjecture (their Conjecture 5.3, stating large dominating number implies an $\overrightarrow{\omega}$-cluster), and establishes logical implications among three related statements, but does not resolve the original conjecture.

Cited literature (1)

partial Clique number of tournaments (2023)

Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes · arXiv preprint · arXiv:2310.04265

Introduces Conjecture 5.3 (large dominating number implies an $\overrightarrow{\omega}$-cluster) as an intermediate statement between Theorem 5.1 and Conjecture 5.2 (the original Problem 4), and establishes implications among the three statements without resolving the conjecture.

Reviewer notes. No paper resolving this conjecture was found. Aboulker et al. 2023 (arXiv:2310.04265) is the main post-2017 work engaging with Problem 4; it situates the conjecture within a broader framework of clique-number and domination-number inequalities in tournaments and introduces a potentially easier intermediate conjecture, but the original statement remains open.

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

Problem. For every integer $k \geq 1$, there exist integers $K$ and $\ell$ such that every tournament $T$ with dominating number at least $K$ contains a subtournament with $\ell$ vertices and dominating number at least $k$.

Context

Theorem 2 shows that sufficiently large dominating number forces a bounded-size subtournament of large chromatic number. The analogous statement with dominating number in place of chromatic number in the conclusion remains open; the note observes that replacing dominating-number hypothesis by large chromatic number alone fails for any $k \geq 3$.

Source paper

Coloring tournaments: from local to global
Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé, Hehui Wu · 2017-03-15
https://arxiv.org/abs/1702.01607 PDF source