1. 引言
本文中涉及的图都是有限无向的简单图。对于边染色图G,若G的每一条边都被染不同的颜色,则称G为彩虹图。对于给定的图G和H,使得G中不存在任何彩虹子图H的最大边染色数,叫做H在G中的anti-Ramsey数,记作AR(G,H)。Anti-Ramsey数是由Erdös等人于上世纪70年代首次提出,并且揭示了图的anti-Ramsey数与Turán数之间密切相关。此外,他们还提出了任意圈在完全图中的anti-Ramsey数的猜想,结论如下:
猜想1.1. [1] 对任意正整数
,都有
。
早期关于anti-Ramsey数的结论主要以完全图为母图,考虑单个图在完全图中的anti-Ramsey数,比如说:路,圈,团,匹配等,可以参考 [2] [3] [4],本文主要介绍关于
的结论。首先,Alon [5]、Jiang & West [6] 解决了完全图中
的anti-Ramsey数,得到如下结论:
定理1.2. [5] [6] 对任意
,都有
。
Axenovich等人 [7] 率先将anti-Ramsey数问题推广到完全二部图,他们证明了完全二部图中任意偶圈的anti-Ramsey数,涉及
的结论如下:
定理1.3. [7] 对任意正整数
都有
。
完全分裂图作为完全多部图的一种特殊情形,短圈
在完全分裂图中的anti-Ramsey数由Lv等人 [8] 证明,结论如下:
定理1.4. [8] 对任意
,以及
,都有
为了下文叙述方便,我们先定义本文中常用的一些图论的术语和符号,并给出一些通用的特殊定义及符号。在图G中,
和
分别为G的顶点集和边集。此外,
,
以及
分别称为顶点数,边数和连通分支数。对于任意点
,与
相关联的边的数目叫做
在G的度,记作
。图G中,点不交的
的最大数量记做
。
若G是一个顶点序列为
的图,且满足两个顶点是邻接的当且仅当它们在顶点的序列是前后相继的,则称G为路,记作
,其中
和
分别叫做路
的起点和终点。而若G可由一条路连接起点和终点得到,则称G为圈,记作
。此外,令
表示G中最大匹配的边数。对于图G和H,若满足
和
,则称H是G的一个子图,记作
。如果
,则H叫做G的生成子图。
对于边染色图G,任意
,令
表示
的颜色。若子图
,则
表示子图H所有边的颜色集合。任意
,从G中删除点
而损失的颜色数叫做点
的饱和度,记作
,即
。若与
相关联的边
,满足
,则称
为
的饱和边。
2. 引理
引理2.1. 设
的部集分别为
,其中
且
。对任意
,都有
证明:设
为
的一个最大匹配,使得
中尽可能多的包含一个端点属于
的边。此外, 令
。显然,
中的所有点都属于同一个部集,否则与
的定义相矛盾。
断言1. 若
,则对任意边
,它都包含一个属于
的端点。
证明:假设存在一个点
和
中的一条边
,使得
,且
。令
。因为
,我们有
。现在我们可以通过增加
,删除
得到一个新的
,这与
的定义相矛盾,断言1证明完毕。
断言2. 若
,则
。
证明:注意
中的所有点都属于同一个部集。假设
且
。令
。因为
,所以必定存在一条边
,使得
。又因为
,我们有
。
现在我们可以由
通过增加两条边
,删除一条边
得到一个更大的匹配,这与
的定义相矛盾。断言2证明完毕。
为了完成证明,下面我们分两种情形进行讨论。
情形1.
。
由断言1可知,
中的所有边都有一个属于
的端点。因此,
,并且此时
。
情形2.
。
由断言2可知,
。因此,
,并且此时
。显然,当
时,
引理2.1证明完毕。
由引理2.1,我们得到如下推论。
推论2.2. 设
,完全多部图
存在完美匹配当且仅当
,或者
且
为偶数。
引理2.3.对任意
,都有
证明:设
为
中包含最大数目点不交的
的集合,使得
中尽可能多的包含一个顶点属于
的
。换言之,在保证数目最大的前提下我们优先挑选那些有一个顶点属于
的
。令
。显然,
中的有点至多属于两个部集,否则与
的定义相矛盾。令
,
。
断言3. 若
,则对任意
,它都包含一个属于
的顶点。
证明:假设存在一个点
,以及
中的一个
,使得
且
。令
。现在我们可以由
通过增加
,删除
来得到一个新的
,这与
的定义相矛盾。
断言3证明完毕。
断言4. 若
,则
。
证明:注意
中的所有点属于至多两个部集。假设
且
。如果
中的所有点属于同一个部集,不失一般性,我们假设
,其中
。因为
,所以
中必定存在两个点不交的
,不妨设为
和
,使得
。现在我们可以由
通过增加
,
,以及
,删除
和
得到一个更大的点不交的
的集合,这与
的定义相矛盾。
因此,
中的所有点恰恰属于两个部集,不失一般性,假设
以及
。因为
,所以
中必定存在一个
,不妨设为
,使得
。现在我们可以由
通过增加
和
,删除
得到一个更大的点不交的
的集合,这与
的定义相矛盾。断言4证明完毕。
为了完成证明,下面我们分三种情形进行讨论。
情形1.
。
由断言3可知,对任意
,它都包含一个属于
的端点。因此,
。另一方面,
中必定存在一个完美匹配。由推论2.2,我们有
或者
且
为偶数。显然,此时
。
情形2.
且
。
由断言3可知,对任意
,它都包含一个属于
的端点。另一方面,因为
,所以
中不存在完美匹配。由推论2.2,我们有
或者
且
为奇数。当
时,
。此外,当
且
为奇数时,
所以
。显然,此时
。
情形3.
。
由断言4可知,
。因为
,所以
且
。显然,此时
。引理2.3证明完毕。
3. 主要结果
基于以上引理,下面开始证明我们的主要结论。
构造3.1. 设
的部集分别为
,其中
,且
。此外,令
,此时我们给出
的一种边染色
,具体染色方法如下:
首先,在
中尽可能多的取出点不交的
,不妨分别设为
,令
表示由剩下的点构成的集合。然后,将
中的所有边都染不同的颜色。最后,对任意
,若
,则将
和
之间的所有边都染新颜色
。
不难发现,由构造3.1给出的
的边染色
中不包含任何彩虹子图
,并且
中恰恰使用了
种颜色。因此,构造3.1表明
中
的anti-Ramsey数不小于
,即
定理 3.2. 对任意
,都有
。
证明:由构造3.1我们已经证明
,因此这里我们只需继续证明
中
的anti-Ramsey数不大于
,即
设
,对
的顶点数
用归纳法。由引理1.2可知,上界对
成立。令
,并假设上界对顶点数小于
也成立。
假设存在一个恰恰使用了
种颜色的
的边染色,使得
中不包含任何彩虹子图
。显然,对任意点
,都有
。注意
不包含任何彩虹子图
。因此,
中也不包含任何彩虹子图
。根据归纳假设可知,
。
因此,对任意点
,都有
(1)
为了完成证明,需要引入下面这些断言。
断言5. 对任意点
,若
是
的两条不同颜色的饱和边,则
和
必定属于不同的部集。
证明:假设存在一个点
,
和
是
的两条颜色不同的饱和边,使得
属于同一个部集。不失一般性,我们假设
。由不等式(1)可知,至少存在
的一条饱和边,不妨设为
,使得
。令
。因为
是
的一条饱和边,所以
。
如果
则
为属于三个不同部集的四个点,其中
。现在我们考虑边
的颜色。不难发现,因为
是
的一条饱和边,可知
。此外,因为
和
是
的两条不同颜色的饱和边,我们有
。因此,此时存在一个彩虹子图
,矛盾。所以
,此时
为属于两个不同部集的四个点,其中
。同理可得,
。因此,此时同样存在一个彩虹子图
,矛盾。断言5证明完毕。
断言6. 对任意点
,都有
。
证明:由不等式(1)可知,对任意点
,都有
。因此,我们只需证明上界
。假设存在一个点
,使得
。不失一般性,设
。由断言5可知,存在至少
的三条颜色不同的饱和边,不妨设为
,使得
,以及
。根据不等式(1)可知,至少存在
的一条饱和边,不妨设为
,使得
。令
。因为
是
的三条颜色不同的饱和边,我们有
。如果
,则
为属于不同部集的四个点。现在我们考虑
的颜色。因为
是
的一条饱和边,可知
。此外,因为
是
的两条颜色不同的饱和边,我们有
。因此,此时存在一个彩虹子图
,矛盾。
因此,
,由
和
的对称性,我们只考虑
或者
这两种情形。如果
,则
为属于三个不同部集的四个点,其中
。同理可得,
。因此,此时存在一个彩虹子图
,矛盾。所以
,则
为属于不同部集的四个点。同理可得
。因此,此时同样存在一个彩虹子图
,矛盾。断言6证明完毕。
断言7. 对任意两个点
,若
是
的饱和边,则
也是
的饱和边。
证明:假设存在两个点
,使得
是
的饱和边,但
不是
的饱和边。令
。由断言5和断言6可知,存在
的一条饱和边,不妨设为
,使得
,其中
。根据断言6,我们有
,所以存在
的两条颜色不同的饱和边,不妨设为
。因为
是
的饱和边,可知
。同时,根据假设可知,
。如果
,则我们考虑边
的颜色。因为
是
的饱和边,可知
。此外,因为
和
是
的两条颜色不同的饱和边,我们有
。因此,此时存在一个彩虹子图
,矛盾。所以
。同理可得,
,这与断言5相矛盾。断言7证明完毕。
断言8. 若
既为
的饱和边,又为
的饱和边,则颜色
只用于染边
。
证明:由饱和边的定义,因为
为
的饱和边,所以颜色
只用于染与 相关联的边。同理,因为
为
的饱和边,所以颜色
只用于染与
相关联的边。因此,颜色
只用于染边
。断言8证明完毕。
令G为
的一个生成子图,使得若
,则
是
的饱和边,或者
是
的饱和边。此外,设
为G任意一个连通分支,其中
。由断言7和断言8可知,对任意
,
只用于染边
。又由断言6可得,对任意点
,都有
,所以G是一个2-正则图。因此,对任意
,
为圈。令
,不妨设
。
断言9. 对任意
,都有
属于同一部集。
证明:显然,
。假设存在
,使得
属于不同部集。现在我们考虑边
的颜色。注意对任意
,
只用于染边
。所以
以及
分别只用于染边
,因此,
。显然,此时存在一个彩虹子图
,矛盾。断言9证明完毕。
由断言9可知,
且
。根据归纳假设可知,对任意点
,
都有
.
因此,对任意点
,都有
这与断言6矛盾。
综上所述,定理3.2证明完毕。