Polynomial dichromatic boundedness under substitution closure
Question 3.10 · arXiv:2310.04265
Status open high confidence
Question 3.10 asks whether polynomial $\overrightarrow{\chi}$-boundedness of a class of tournaments is preserved under substitution closure, in analogy with the result of Chudnovsky et al. for undirected graphs. The source paper itself establishes that (non-polynomial) $\overrightarrow{\chi}$-boundedness is preserved under substitution but only with an exponential binding function $g(w)=(3wf(w))^w$, motivating the question. No follow-up paper resolving Question 3.10 was found in the indexed literature as of May 2026.
Reviewer notes. A related 2026 paper arXiv:2602.09863 ('Characterizing Large Clique Number in Tournaments') answers a different question from the same source paper (about certification of large clique number by bounded-size sets), not Question 3.10. The paper arXiv:2401.07776 establishes NP-completeness of computing clique number of tournaments and refutes a different conjecture from Aboulker et al. 2023. Question 3.10 on polynomial preservation under substitution closure remains open with no follow-up found.
Context
The hereditary closure of $\{\widetilde{S}_{n},n\in\mathbb{N}\}$ equals $\{TT_{1},TT_{2},\overrightarrow{C_{3}}\}^{subst}$, which satisfies an exponential bound, and it is open whether the order of magnitude $(3/2)^n$ of $\operatorname{\overrightarrow{\chi}}(\widetilde{S}_n)$ can be reduced to a polynomial. The question asks whether polynomial $\operatorname{\overrightarrow{\chi}}$-boundedness is preserved under substitution closure.
Source paper
Clique number of tournaments
Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes · 2023-10-06
https://arxiv.org/abs/2310.04265