Aharoni's rainbow cycle conjecture holds up to an additive constant
Preprint
Abstract
In 2017, Aharoni proposed the following generalization of the Caccetta-H\"{a}ggkvist conjecture: if $G$ is a simple $n$-vertex edge-colored graph with $n$ color classes of size at least $r$, then $G$ contains a rainbow cycle of length at most $\lceil n/r \rceil$. In this paper, we prove that, for fixed $r$, Aharoni's conjecture holds up to an additive constant. Specifically, we show that for each fixed $r \geq 1$, there exists a constant $c_r$ such that if $G$ is a simple $n$-vertex edge-colored graph with $n$ color classes of size at least $r$, then $G$ contains a rainbow cycle of length at most $n/r + c_r$.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Notes on Aharoni’s rainbow cycle conjecture2024
- Further Approximations for Aharoni's Rainbow Generalization of the Caccetta-Häggkvist ConjectureThe Electronic Journal of Combinatorics, 2022
- Short rainbow cycles in graphs and matroidsJournal of Graph Theory, 2020
- Rainbow triangles and the Caccetta‐Häggkvist conjectureJournal of Graph Theory, 2019
- On the Caccetta-Häggkvist ConjectureGraphs and Combinatorics, 2002
- Girth of sparse graphsJournal of Graph Theory, 2002
- On the girth of digraphsDiscrete Mathematics, 2000