Back to Search
Start Over
Non-uniform degrees and rainbow versions of the Caccetta-H\'aggkvist conjecture
- 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 :
- Mathematics - Combinatorics
Subjects
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