Digraph H-subgraph via χ and out-degree

Question 4.1 · arXiv:2503.20045

arXiv Question high confidence— first stated 2025-03-25

Authors: Hidde Koerts, Benjamin Moore, Sophie Spirkl

Status open high confidence

Question 4.1 from arXiv:2503.20045 asks for which fixed digraphs H there exists a constant c_ε ≥ 1 for all ε > 0 such that every digraph D with χ(D) ≥ c_ε and minimum out-degree at least ε|V(D)| contains H as a subdigraph; this generalises the paper's main result (Theorem 1.3), which settles the question for all cycle orientations. The paper itself notes two families with affirmative answers: the cycle orientations characterised by Theorem 1.3, and subdigraphs of directed complete bipartite digraphs. No follow-up paper addressing the general question was found.

Reviewer notes. The source paper was published in Combinatorica 46, 12 (2026) (doi:10.1007/s00493-026-00207-0). Question 4.1 is a broad open problem posed in the paper; the characterisation for cycle orientations (Theorem 1.3) and the Ramsey-type argument for subdigraphs of directed complete bipartite digraphs are the only known partial answers. No follow-up resolving the general question was found in the indexed literature as of 2026-05-14.

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

Question. For which fixed digraphs $H$ does there exist a constant $c_{\varepsilon}\geq 1$ for all $\varepsilon>0$ such that every digraph $D$ without loops or parallel arcs with $\chi(D)\geq c_{\varepsilon}$ and minimum out-degree at least $\varepsilon|V(D)|$ contains $H$ as a subdigraph?

Context

This is a more general version of Question 1.2, replacing cycle orientations by arbitrary fixed digraphs $H$. Theorem 1.3 characterizes the orientations of cycles for which this question is answered affirmatively. The authors also note that all subdigraphs of directed complete bipartite digraphs (with uniform arc orientation between parts) give an affirmative answer via a Ramsey-type argument.

Source paper

Orientations of cycles in digraphs of high chromatic number and high minimum out-degree
Hidde Koerts, Benjamin Moore, Sophie Spirkl · 2025-03-25
https://arxiv.org/abs/2503.20045