Proved
Established result in cited source ↗
Observed Oct 12, 2026
Theorem · version 1
Why the rainbow conjecture would imply the directed bound
Statement
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.
Assumptions
- 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.
Evidence
Source reports
Connections
In this problem · publication v8 · Selected context
Caccetta–Häggkvist cycle bound →
Conditional implication · Proved
One-way implication
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.
Details & sources
Aharoni’s rainbow cycle conjecture →
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⌉.
- A rainbow cycle uses pairwise distinct edge colors; this is a stronger conjecture in a different graph setting.
Scope: A rainbow cycle uses pairwise distinct edge colors; this is a stronger conjecture in a different graph setting.
The full directed cycle bound →
Open · version 1
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⌉?
- 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.
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.
Why the rainbow conjecture would imply the directed bound →
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.
- 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.
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 →Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v11
Caccetta–Häggkvist cycle bound →
Conditional implication · Proved
One-way implication
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.
Details & sources
Aharoni’s rainbow cycle conjecture →
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⌉.
- A rainbow cycle uses pairwise distinct edge colors; this is a stronger conjecture in a different graph setting.
Scope: A rainbow cycle uses pairwise distinct edge colors; this is a stronger conjecture in a different graph setting.
The full directed cycle bound →
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⌉?
- 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.
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.
Why the rainbow conjecture would imply the directed bound →
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.
- 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.
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 →Relationship not independently reviewed. This concerns its use in this problem.
Sources
Aharoni’s rainbow cycle conjecture holds up to an additive constant →
- §1, Conjectures 1.1 and 1.3; reduction following Conjecture 1.3 → · Original passage ↗
Recorded wording
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.
Revision & attribution
Source revision: arxiv-2212.05697v4. Observed Oct 12, 2026.
AI use is not reported in the selected source.
AIM · Caccetta–Häggkvist workshop survey →
- Page 2, Conjecture 2.1 → · Original passage ↗
Recorded wording
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
AIM · Caccetta–Häggkvist workshop survey →
- Page 2, Conjecture 2.1 → · Original passage ↗
Recorded wording
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
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
Established result in cited source ↗
Observed Oct 12, 2026 · Source passage →
Record details
- Claim ID
- claim-ch-rainbow-implies-directed
- Statement version
- 1
- SHA-256
- d53e5038a32a7759324a5610534e2f5b73bdad2201aafd7b9fa0c519abe88ae3