Reading source record arxiv-2212.05697v4. View default cited record →
Aharoni’s rainbow cycle conjecture holds up to an additive constant
Source-backed selection; publication and proof assessment are separate.
The exact passages cited in OpenMath. Each passage identifies how its wording was recorded.
For each fixed positive integer r, the authors prove a rainbow cycle bound n/r + α_r, with a constant depending on r and growth O(r⁵ log² r). This leaves the sharp ceiling bound unresolved.
Passage ID: caccetta-haggkvist:entry:rainbow-additive:v1
Source item: Corollary 1.8; r = 1 discussed in its proof
Source record: hompe-huynh-rainbow@arxiv-2212.05697v4
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.
Passage ID: caccetta-haggkvist:entry:rainbow:v1
Source item: §1, Conjectures 1.1 and 1.3; reduction following Conjecture 1.3
Source record: hompe-huynh-rainbow@arxiv-2212.05697v4
Explicit citations in versioned problem publications. A citation records a use; it does not confer proof or independent verification.
Problem publication v11
Source assessment
Proved
Established result in cited source
The constant depends on r and is not removed by this theorem.
Observed Oct 12, 2026
Source assessment
Open
Open question in cited source
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 assessment
Proved
Established result in cited source
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.
Observed Oct 12, 2026
Connection
A rainbow cycle in the tail-colored graph gives a directed cycle of the same length.
Source assessment
Open
Open question in cited source
A rainbow cycle uses pairwise distinct edge colors; this is a stronger conjecture in a different graph setting.
Observed Oct 12, 2026
History
Rainbow cycles with an additive error
Question
Caccetta–Häggkvist cycle bound
Connection
The one-third triangle question is a specialization for oriented graphs.
Recorded authorship
Patrick Hompe · Tony Huynh
Patrick Hompe; Tony Huynh
AI use is not reported in the selected source.
OpenMath source records preserve exact citations. Observation dates order these records; they do not establish the latest upstream paper or proof.
Aharoni’s rainbow cycle conjecture holds up to an additive constant
Follow the original source for authoritative statements and reuse terms.
Source terms ↗