APP下载

一些联图的anti-Ramsey数

2021-10-29丁吉丽于海征

厦门大学学报(自然科学版) 2021年6期
关键词:种颜色子图情形

丁吉丽,边 红*,于海征

(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.

展开全文▼

猜你喜欢

种颜色子图情形
关于丢番图方程x3+1=413y2*
有限二阶矩情形与重尾情形下的Hurst参数
观察:颜色数一数
临界情形下Schrödinger-Maxwell方程的基态解
k元n立方体的条件容错强Menger边连通性
临界完全图Ramsey数
不含3K1和K1+C4为导出子图的图色数上界∗
关于l-路和图的超欧拉性
图G(p,q)的生成子图的构造与计数
迷人的颜色