χ̄-boundedness closed under substitution
Conjecture 6.1 · arXiv:2310.04265
Status open high confidence
Conjecture 6.1 asks whether the class of $\overrightarrow{\chi}$-bounded digraphs is closed under substitution in full generality. The tournament case is already settled affirmatively by Theorem 3.9 of the source paper, which shows that if a tournament class is $\overrightarrow{\chi}$-bounded then so is its closure under substitution (with an explicit bound). The authors note that key tools used for tournaments fail for general digraphs, so the conjecture remains open for the broader digraph setting. No follow-up paper addressing the general digraph case was found in the indexed literature.
Reviewer notes. The tournament case is already proven in the source paper (Theorem 3.9): if a tournament class is $\overrightarrow{\chi}$-bounded by function $f$, its closure under substitution is $\overrightarrow{\chi}$-bounded by $g(w)=(3wf(w))^w$. Conjecture 6.1 is the generalisation to all digraphs; the authors note that Theorem 3.3 (a key ingredient for tournaments) does not hold for general digraphs, making the full conjecture harder. No follow-up paper resolving or substantially advancing the general digraph case was found after a targeted web search.
Context
In the concluding section the authors generalise Question 3.10 (which asked the same for tournaments) to all digraphs. They note that Theorem 3.3 does not hold for general digraphs, making the digraph setting harder, and discuss partial positive evidence from the tournament case.
Source paper
Clique number of tournaments
Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes · 2023-10-06
https://arxiv.org/abs/2310.04265