一些联图的anti-Ramsey数

丁吉丽,边 红*，于海征

(1.新疆师范大学数学科学学院，新疆 乌鲁木齐 830017;2.新疆大学数学与系统科学学院，新疆 乌鲁木齐 830046)

1 预备知识

图的anti-Ramsey数是由Erdös等[1]在1973年提出的.若将图G的边染色中所有的边都染成不同的颜色，则称图G是彩虹的.图G的anti-Ramsey数ar(G，H)是指图G的边染色中所用的最大颜色数，使得图G不包含彩虹子图H[1].Erdös等[1]最初研究anti-Ramsey数的母图是完全图，且对完全图中的圈和路的anti-Ramsey数提出猜想，并阐明了图的anti-Ramsey数和图的Turn数之间有着密切的联系.图H的Turn数ex(n，H)是指n个顶点的图中所包含的最大边数，使得该图不包含同构于H的子图[2].

沿着这条研究主线，学者们研究了完全图中的其他图类的anti-Ramsey数，比如：树[3]、小的二部图[4]、点不交的圈[5]、匹配[6-8]等.后来，研究anti- Ramsey问题的母图从完全图变换成其他的图类，比如完全二部图[9-11]、完全分裂图[12]、超立方体[13]、平面三角剖分图[14]、超图[15]等.

在图G中，对于∀v∈V(G)，∀e∈E(G).用C(G)表示图G所有边的颜色的集合；C(v)表示与顶点v相关联的边的颜色的集合，c(e)表示边e的颜色.G1和G2是图G中两个不同的子图，E(G1，G2)表示一个端点在G1中，另一个端点在G2中的所有边的集合,C(G1,G2)表示E(G1，G2)中所有边的颜色的集合.

2 主要结果

2.1 联图的anti-Ramsey数

因为C3=K3,所以由定理1易得定理2.

定理3[14]若n≥4,则ar(Wn,C3)=n+1.

定理6[9]若n≤s,k≤2,则

ar(Kn,s,C2k)=

对于n=4的情形，用ar(Kn,s，C4)种颜色对Kn,s的边染色，使得Kn,s不包含彩虹的子图C4,用一种新颜色对Cn的边染色，使得Cn是一个单色图.

下面根据n的奇偶进行分类讨论：

情形1n是奇数.

情形2n是偶数.

若c(x2zi)=2,则c(xmzi)=2,其中m=2,4,6,…，n;

若c(x2zi)=1,则c(xmzi)=1,其中m=1,2,3,…,n-1,n.

2.2 联图的anti-Ramsey数

引理1[14]若Ck是边着色图G中的一个彩虹圈且k≥4,如果G[Ck]有一条弦，则在G中有一个长度小于k的彩虹圈.

彩虹的C3的位置有两种，如图1所示.

图中C3的两种位置Fig.1 Two location of C3 in

情形1彩虹C3位于前一种位置(图1(a)).

情形2彩虹C3位于后一种位置(图1(b)).

2.3 联图的anti-Ramsey数

图中C4的3种位置Fig.2 Three location of C4 in

2.4 联图的anti-Ramsey数

定理20若n≥2,则ar(Fn，C3)=2n.

证明对于友谊图Fn，实质上是n个三角形有一个公共顶点的图.按照这样的特性，用n种颜色将每个三角形中和公共顶点关联的两条边染成一样的颜 色，剩余的n条边用新的n种不同的颜色染色，此时在Fn中一定不含彩虹的C3.因此,ar(Fn，C3)≥2n.

如果用2n+1种颜色对Fn的边任意染色，根据鸽巢原理，那么至少有一个三角形的3条边颜色不一样，即找到一个彩虹的C3.因此，ar(Fn，C3)<2n+1.