Cycle orientations in high chromatic high out-degree digraphs

Question 1.2 · arXiv:2503.20045

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

Authors: Hidde Koerts, Benjamin Moore, Sophie Spirkl

Status solved high confidence

Question 1.2 is fully answered within the source paper itself by Theorem 1.3, which characterizes all orientations of cycles $C$ that must appear as subdigraphs in every digraph $D$ (without loops or parallel arcs) with $\chi(D) \geq c$ and minimum out-degree at least $\varepsilon|V(D)|$ for fixed $\varepsilon > 0$, generalizing a result of Thomassen. The paper has been peer-reviewed and published in Combinatorica 46 (2026).

Reviewer notes. Question 1.2 is self-contained: it is posed and fully resolved by Theorem 1.3 within the same paper. The paper was accepted by Combinatorica (DOI: 10.1007/s00493-026-00207-0, accepted 10 February 2026, published 4 March 2026). A related arXiv preprint 2509.07760 (Xue, 2025) studies chromatic profiles of oriented cycles but was not confirmed to cite or extend Question 1.2 specifically.

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

Question. Which orientations of cycles are contained in every digraph with high minimum out-degree and high chromatic number?

Context

This is the central question of the paper, investigating a directed analogue of the chromatic threshold for cycles. The authors consider digraphs $D$ without loops or parallel arcs with minimum out-degree at least $\varepsilon|V(D)|$ for fixed $\varepsilon>0$. Theorem 1.3 in this paper fully answers Question 1.2.

Notes. This question is fully resolved within the same paper by Theorem 1.3; included because it is a labelled question environment and the central research question.

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