Directed chromatic threshold for digraph subgraphs

Question 4.2 · 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.2 defines the directed chromatic threshold ε_H for a fixed digraph H as the minimum ε ≥ 0 such that digraphs with sufficiently high chromatic number and minimum out-degree at least ε|V(D)| must contain H as a subdigraph. The source paper itself settles the ε_H = 0 case for orientations of cycles (Theorem 1.3); the general question for arbitrary digraphs H remains open. A September 2025 follow-up (arXiv:2509.07760) studies the closely related notion of chromatic profiles δ_χ^+(H, k) for oriented cycles, proving exact thresholds for transitive tournaments and specific oriented cycles, and explicitly cites the source paper—but does not resolve Question 4.2 in general.

Cited literature (1)

partial A directed Andrásfai-Erdős-Sós theorem and chromatic profiles of oriented cycles (2025)

unverified (not extracted from fetch) · arXiv preprint · arXiv:2509.07760

Introduces and studies chromatic profiles δ_χ^+(H, k) for oriented cycles—a refinement of the directed chromatic threshold—proving exact out-degree thresholds for transitive tournaments and several oriented cycles; cites arXiv:2503.20045 for the ε_H = 0 characterisation but does not resolve ε_H for general digraphs H.

Reviewer notes. Question 4.2 is a broad open research question rather than a specific conjecture: it asks for ε_H for every fixed digraph H. The source paper itself resolves the ε_H = 0 case for oriented cycles. The closely related chromatic profile δ_χ^+(H, k) studied in arXiv:2509.07760 provides partial progress on the structure of the threshold for specific oriented cycles. The source paper was published in Combinatorica (Springer, 2026, doi:10.1007/s00493-026-00207-0).

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

Question. For a fixed digraph $H$, what is the minimum value $\varepsilon_{H}\geq 0$ such that there exists a constant $c\geq 1$ such that every digraph $D$ without loops or parallel arcs with $\chi(D)\geq c$ and minimum out-degree at least $\varepsilon_{H}|V(D)|$ contains $H$ as a subdigraph?

Context

The quantity $\varepsilon_H$ provides a directed analogue of the chromatic threshold studied for undirected graphs. Theorem 1.3 may be interpreted as characterizing the orientations of cycles for which the directed chromatic threshold $\varepsilon_H$ equals zero. The authors also suggest studying variants where high chromatic number is replaced by high dichromatic number.

Notes. The authors note that $\varepsilon_H = 1$ is always an upper bound, so the quantity is well-defined for all digraphs $H$.

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