## Abstract

The Caccetta-Häggkvist conjecture (denoted CHC) states that the directed girth (the smallest length of a directed cycle) dgirth(D) of a directed graph D on n vertices is at most (equation presented)⌈^{n}_{δ+(D)}⌉, where δ^{+}(D) is the minimum outdegree of D. We consider a version involving all outdegrees, not merely the minimum one, and prove that if D does not contain a sink, then dgirth(D) ≤ 2 (equation presented)-_{v∊V(D) deg+}^{1}_{(v)+1}. In the spirit of a generalization of the CHC to rainbow cycles in [1], this suggests the conjecture that given nonempty sets F_{1},..., F_{n} of edges of K_{n}, there exists a rainbow cycle of length at most 2 (equation presented)-_{1≤i≤n} |F_{i}^{1} | _{+1}. We prove a bit stronger result when 1 ≤ | F_{i}| ≤ 2, thereby strengthening a result of DeVos et al. [J. Graph Theory, 96 (2021), pp. 192-202]. We prove a logarithmic bound on the rainbow girth in the case that the sets Fi are triangles.

Original language | English (US) |
---|---|

Pages (from-to) | 1704-1714 |

Number of pages | 11 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 37 |

Issue number | 3 |

DOIs | |

State | Published - 2023 |

## All Science Journal Classification (ASJC) codes

- General Mathematics

## Keywords

- directed girth
- generalized Caccetta-Häggkvist conjecture
- rainbow girth