Proper-incident short rainbow cycle bound

Conjecture 4 · arXiv:1806.00825

arXiv Conjecture medium confidence— first stated 2020-05-07

Authors: Matt DeVos, Matthew Drescher, Daryl Funk, Sebastián González Hermosillo de la Maza, Krystal Guo, Tony Huynh, Bojan Mohar, Amanda Montejano

Status open medium confidence

Conjecture 4 from arXiv:1806.00825, which asks for a short proper cycle (no two incident edges share a color) of length at most \lceil n/r \rceil in an n-vertex graph with n color classes each of size at least r, remains open as a specific target. It is strictly weaker than Aharoni's rainbow cycle conjecture. Progress on Aharoni's conjecture — proven for color class size \Omega(k \log k) by Hompe et al. (2021) and advanced further in 2024 — is indirectly relevant but does not settle Conjecture 4. No paper directly addressing the proper-cycle variant was found in the searched literature.

Cited literature (1)

partial On Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture (2021)

Patrick Hompe, Petra Pelikanova, Aneta Pokorna, Sophie Spirkl · Discrete Mathematics, Volume 344, Issue 5 · arXiv:2101.04716

Proves Aharoni's rainbow conjecture (strictly stronger than Conjecture 4) when each color class has size at least \Omega(k \log k); only indirectly relevant to Conjecture 4 via the implication that a solved stronger conjecture would settle the weaker one.

Reviewer notes. Conjecture 4 requires only that no two incident edges of the found cycle share a color (proper edge-coloring condition on the cycle), which is strictly weaker than Aharoni's rainbow condition (all edges distinct colors). No dedicated follow-up paper addressing this proper-cycle variant was found. A 2024 JCTB paper ('Aharoni's rainbow cycle conjecture holds up to an additive constant', doi:10.1016/j.jctb.2024.12.004) and a 2022 result showing Aharoni's conjecture holds for \Omega(k) color class size advance the stronger rainbow conjecture, but access to the 2024 paper was blocked (HTTP 403) and it cannot be cited as verified. Confidence is medium because the 2024 JCTB paper may implicitly cover Conjecture 4 but could not be confirmed.

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

Conjecture. Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $r$. Then $(G, c)$ contains a cycle $C$ of length at most $\lceil n/r \rceil$ such that no two incident edges of $C$ are the same colour.

Context

Introduced by the authors as a weakening of Aharoni's Conjecture 3 (the rainbow condition on the whole cycle is replaced by a proper-edge-colouring condition on incident pairs). The authors prove that Conjecture 4 implies the Caccetta-Häggkvist conjecture via a direct colouring construction on the underlying undirected graph of a digraph.

Notes. PDF source — ceiling notation garbled but mathematical content is unambiguous.

Source paper

Short rainbow cycles in graphs and matroids
Matt DeVos, Matthew Drescher, Daryl Funk, Sebastián González Hermosillo de la Maza, Krystal Guo, Tony Huynh, Bojan Mohar, Amanda Montejano · 2020-05-07
https://arxiv.org/abs/1806.00825 PDF source