论文标题
关于Aharoni的彩虹循环的笔记猜想
Notes on Aharoni's rainbow cycle conjecture
论文作者
论文摘要
在2017年，罗恩·阿哈罗尼（Ron Aharoni）对边缘颜色图中的彩虹循环做出了以下猜想：如果$ g $是$ n $ vertex图形，其边缘的边缘颜色为$ n $颜色，每个颜色类别至少$ r $，那么$ g $，则最多包含$ \ lceil \ lceil \ lceil \ frac \ frac \ frac $ frac $ freac $ freac $ freac $ freac $。研究Aharoni的猜想的一种动机是，这是从1978年开始对Digraphs的Caccetta-Häggkvist的加强。 在本文中，我们介绍了Aharoni的猜想的调查，其中包括许多最近的部分结果和相关的猜想。我们还提出了两个新的结果。我们的主要新结果是$ r = 3 $ case of Aharoni的猜想。我们证明，如果$ g $是$ n $ vertex图，其边缘的颜色为$ n $颜色，并且每个颜色类的大小至少3个，则$ g $包含一个长度的彩虹循环，最多最多$ \ frac {4n} {9} {9}+7 $。我们还讨论了我们的方法如何推广到$ r $的较大值。
In 2017, Ron Aharoni made the following conjecture about rainbow cycles in edge-coloured graphs: If $G$ is an $n$-vertex graph whose edges are coloured with $n$ colours and each colour class has size at least $r$, then $G$ contains a rainbow cycle of length at most $\lceil \frac{n}{r} \rceil$. One motivation for studying Aharoni's conjecture is that it is a strengthening of the Caccetta-Häggkvist conjecture on digraphs from 1978. In this article, we present a survey of Aharoni's conjecture, including many recent partial results and related conjectures. We also present two new results. Our main new result is for the $r=3$ case of Aharoni's conjecture. We prove that if $G$ is an $n$-vertex graph whose edges are coloured with $n$ colours and each colour class has size at least 3, then $G$ contains a rainbow cycle of length at most $\frac{4n}{9}+7$. We also discuss how our approach might generalise to larger values of $r$.
