小边集族的短彩虹圈-计算机科学-图论-算法.pdfVIP

小边集族的短彩虹圈

HEGUO

摘要.2019年，Aharoni提出了一个推广Caceetta-Häggkvist猜想的猜想：如果

一个具有个顶点的图允许一种边着色（不一定适当）使用种颜色，使得每个颜

色类的大小至少为，那么包含长度不超过的彩虹圈。近期的工作[3,1,8]

表明，如果颜色类别中有一部分是非星型的，则彩虹周长是log。在这篇笔记

中，我们扩展了这些结果，并表明即使非星型的颜色类别的比例很小也足以确保对

数级的彩虹周长。我们也证明了这个对数界限是正确量级的。此外，我们确定了颜

本色类别类型之间的阈值比率，在该比率下，彩虹周长从线性过渡到对数。

译

中

1.介绍

1

v

1以下是在图论中由Caccetta和Häggkvist于1978年提出的一个著名猜想。

8[5]

5

4

0猜想1([5]).在一个具有最小出度的顶点有向图中，存在一个长度最多为

.

7的有向圈。

0

5

2该猜想仍然未解决。关于此问题的研究历史，请参见例如[11,12,13]中的

:参考文献。

v

i给定一个图和一种边着色（不一定是正确的）使用种颜色

x

r

a，对于每个边集被称为颜色类，并且子图的是彩虹如

果中的任意两条边不属于同一颜色类。彩虹周长的是在中彩虹圈的最

小长度，如果不存在彩虹圈则定义为。在[2]中，Aharoni提出了Caccetta-

Häggkvist猜想的一个推广。

猜想2([2]).对于一个有个顶点的图和一种使用种颜色对进行边着

色的方式，如果每个颜色类的大小至少为，那么彩虹周长至多为。

请参阅[3]以了解证明，为什么猜想2意味着猜想1。并且如果猜想2成立，

那么该界是紧的：考虑在上具有个顶点的图，并且每个颜色类

的形式为对于，其中索引取模。

Date:2025年6月.

DepartmentofMathematicsandMathematicalStatistics,UmeåUniversity,Umeå90187,Sweden.

E-mail:he.guo@umu.se.ResearchsupportedbytheKempeFoundationgrantJCSMK23-0055.

1

2