Conjecture · version 2
Must a simple directed graph with n vertices and minimum out-degree at least r ≥ 1 contain a directed cycle of length at most ⌈n/r⌉?
Open
The published 2025 paper presents the full directed cycle bound as an open conjecture; partial results below retain their own assumptions.
Observed Oct 12, 2026
Replaces an earlier source assessment. Version history ↓
In this problem · publication v11 · Selected context
Primary formulation · Open
A rainbow cycle in the tail-colored graph gives a directed cycle of the same length.
This implication is proved; its rainbow premise remains unproved.
Open · version 1
Every simple undirected graph on n ≥ 1 vertices whose edges are partitioned into n color classes of size at least an integer r ≥ 1 contains a rainbow cycle of length at most ⌈n/r⌉.
Scope: A rainbow cycle uses pairwise distinct edge colors; this is a stronger conjecture in a different graph setting.
Open · version 2
Must a simple directed graph with n vertices and minimum out-degree at least r ≥ 1 contain a directed cycle of length at most ⌈n/r⌉?
Scope: Finite directed graphs with no loops or parallel arcs; opposite arcs are allowed and already give a cycle of length two. Here n is the number of vertices and r is a positive integer lower bound on every vertex’s out-degree. The cycle visits distinct vertices, and ⌈n/r⌉ is rounded up.
Relationship statement · Proved · version 1
If Aharoni’s rainbow cycle conjecture holds for all n and r, then the Caccetta–Häggkvist directed cycle bound holds for all n and r.
Scope: Handle an opposite-arc cycle first; otherwise forget directions and color each edge by its tail. Distinct colors on a cycle force one outgoing edge at each cycle vertex.
Relationship not independently reviewed.
Connection in Caccetta–Häggkvist cycle bound →The one-third triangle question is a specialization for oriented graphs.
Settling this specialization alone would not settle every n and r.
Open · version 2
Must a simple directed graph with n vertices and minimum out-degree at least r ≥ 1 contain a directed cycle of length at most ⌈n/r⌉?
Scope: Finite directed graphs with no loops or parallel arcs; opposite arcs are allowed and already give a cycle of length two. Here n is the number of vertices and r is a positive integer lower bound on every vertex’s out-degree. The cycle visits distinct vertices, and ⌈n/r⌉ is rounded up.
Open · version 1
Every finite oriented graph on n ≥ 1 vertices with minimum out-degree at least n/3 contains a directed triangle.
Scope: Oriented graphs have no loops, parallel arcs or opposite arcs; this is a specialization of the full conjecture.
Relationship not independently reviewed.
Connection in Caccetta–Häggkvist cycle bound →Relationship not independently reviewed. This concerns its use in this problem.
Must a simple directed graph with n vertices and minimum out-degree at least r ≥ 1 contain a directed cycle of length at most ⌈n/r⌉?
paraphrase · Store metadata and original OpenMath paraphrases; follow the original source for authoritative wording.
Blair D. Sullivan; hosted by American Institute of Mathematics · Revision 2006-04-14-sha256-98251ac3
The rainbow conjecture asks for a cycle with distinct edge colors and length at most ⌈n/r⌉ when n color classes in a simple n-vertex graph each have at least r edges. Coloring directed edges by their tails shows this would imply the Caccetta–Häggkvist conjecture.
paraphrase · Follow the original source for authoritative statements and reuse terms.
Patrick Hompe · Tony Huynh · Published · Publication date May 2025
Source-backed selection; publication and proof assessment are separate.
Source revision: arxiv-2212.05697v4. Observed Oct 12, 2026.
AI use is not reported in the selected source.
The triangle specialization asks for a directed triangle at minimum out-degree at least one third of the vertex count, in an oriented graph.
paraphrase · Follow the original source for authoritative statements and reuse terms.
Jan Hladký · Daniel Král’ · Sergey Norin · Published · Publication date 2017
Source-backed selection; publication and proof assessment are separate.
Source revision: arxiv-0908.2791v4. Observed Oct 12, 2026.
AI use is not reported in the selected source.
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Open
The published 2025 paper presents the full directed cycle bound as an open conjecture; partial results below retain their own assumptions.
Observed Oct 12, 2026 · Source passage →
Replaces an earlier source assessment; see the original source for its history.