Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2110.11183 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911953729880064 |
|---|---|
| author | Aharoni, Ron Berger, Eli Chudnovsky, Maria Guo, He Zerbib, Shira |
| author_facet | Aharoni, Ron Berger, Eli Chudnovsky, Maria Guo, He Zerbib, Shira |
| contents | The Caccetta-Häggkvist 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}{δ^+(D)}\rceil$, where $δ^+(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_11183 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Non-uniform degrees and rainbow versions of the Caccetta-Häggkvist conjecture Aharoni, Ron Berger, Eli Chudnovsky, Maria Guo, He Zerbib, Shira Combinatorics The Caccetta-Häggkvist 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}{δ^+(D)}\rceil$, where $δ^+(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. |
| title | Non-uniform degrees and rainbow versions of the Caccetta-Häggkvist conjecture |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2110.11183 |