Nonuniform Degrees and Rainbow Versions of the Caccetta–Häggkvist Conjecture

Abstract

The Caccetta–Häggkvist conjecture (denoted CHC) states that the directed girth (the smallest length of a directed cycle) of a directed graph on vertices is at most , where is the minimum outdegree of . We consider a version involving all outdegrees, not merely the minimum one, and prove that if does not contain a sink, then . In the spirit of a generalization of the CHC to rainbow cycles in [1], this suggests the conjecture that given nonempty sets of edges of , there exists a rainbow cycle of length at most . We prove a bit stronger result when , 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 are triangles.

Locations

• SIAM Journal on Discrete Mathematics - View
• arXiv (Cornell University) - View - PDF