Dichromatic construction size in C₃
Open problem on construction size · arXiv:2202.01006
Status open high confidence
No follow-up work was found that reduces the $n^{2^{\mathrm{poly}(n)}}$ size bound for the $(k+1)$-dichromatic construction in $\mathcal{C}_3$ from arXiv:2202.01006. The paper appeared in the Electronic Journal of Combinatorics (v29i2p17, 2022). Related work (arXiv:2309.17385, Bessy–Havet–Picasarri-Arrieta, 2023) studies dichromatic numbers of chordal graph orientations but does not address this specific size-reduction question. The open problem of closing the gap between $n^{2^{\mathrm{poly}(n)}}$ and the $2^{\mathrm{poly}(|G_k|)}$ Zykov bound for triangle-free undirected graphs appears unresolved.
Reviewer notes. No follow-up found addressing the specific size-reduction question. The paper arXiv:2309.17385 ('Dichromatic number of chordal graphs', Bessy–Havet–Picasarri-Arrieta, 2023) is thematically related but its abstract does not reference the construction size open problem from 2202.01006.
Context
The authors observe in the Further Works section that their Zykov-style digraph construction yields graphs whose size grows much faster than the analogous triangle-free undirected graphs, and they flag reducing this size as an open problem.
Notes. PDF source — the size expression appears as 'n2poly(n)' in the extraction; the exact exponent tower has been reconstructed as $n^{2^{\mathrm{poly}(n)}}$ based on the Lemma 3 bound $n^{4r}$ and the recursive structure, but may differ from the original LaTeX.
Source paper
Chordal directed graphs are not $χ$-bounded
Pierre Aboulker, Nicolas Bousquet, Rémi de Verclos · 2022-02-02
https://arxiv.org/abs/2202.01006
PDF source