NONUNIFORM DEGREES AND RAINBOW VERSIONS OF THE CACCETTA-HÄGGKVIST CONJECTURE

Ron Aharoni, Eli Berger, Maria Chudnovsky, He Guo, Shira Zerbib

Research output: Contribution to journalArticlepeer-review

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 F1,..., Fn of edges of Kn, there exists a rainbow cycle of length at most 2 (equation presented)-1≤i≤n |Fi1 | +1. We prove a bit stronger result when 1 ≤ | Fi| ≤ 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 languageEnglish (US)
Pages (from-to)1704-1714
Number of pages11
JournalSIAM Journal on Discrete Mathematics
Volume37
Issue number3
DOIs
StatePublished - 2023

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

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

Fingerprint

Dive into the research topics of 'NONUNIFORM DEGREES AND RAINBOW VERSIONS OF THE CACCETTA-HÄGGKVIST CONJECTURE'. Together they form a unique fingerprint.

Cite this