Back to Search Start Over

Non-uniform degrees and rainbow versions of the Caccetta-H\'aggkvist conjecture

Authors :
Aharoni, Ron
Berger, Eli
Chudnovsky, Maria
Guo, He
Zerbib, Shira
Source :
SIAM Journal on Discrete Mathematics 37 (2023), 1704--1714
Publication Year :
2021

Abstract

The Caccetta-H\"aggkvist conjecture (denoted below 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 $\lceil \frac{n}{\delta^+(D)}\rceil$, where $\delta^+(D)$ is the minimum out-degree of~$D$. We consider a version involving all out-degrees, not merely the minimum one, and prove that if $D$ does not contain a sink, then $dgirth(D) \le 2 \sum_{v\in V(D)} \frac{1}{deg^+(v)+1}$. In the spirit of a generalization of the CHC to rainbow cycles in \cite{ADH2019}, this suggests the conjecture that given non-empty sets $F_1, \ldots,F_n$ of edges of $K_n$, there exists a rainbow cycle of length at most $2\sum_{1\le i \le n}\frac{1}{|F_i|+1}$. We prove a bit stronger result when $1\le |F_i|\le 2$, thereby strengthening a result of DeVos et. al \cite{DDFGGHMM2021}. We prove a logarithmic bound on the rainbow girth in the case that the sets $F_i$ are triangles.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Journal :
SIAM Journal on Discrete Mathematics 37 (2023), 1704--1714
Publication Type :
Report
Accession number :
edsarx.2110.11183
Document Type :
Working Paper
Full Text :
https://doi.org/10.1137/22M1529658