一类极小连通图的Anti-Ramsey数

段春燕,苗连英(.华中农业大学楚天学院,武汉43005;.中国矿业大学理学院,江苏徐州008)

一类极小连通图的Anti-Ramsey数

段春燕1,苗连英2
(1.华中农业大学楚天学院,武汉430205;2.中国矿业大学理学院,江苏徐州221008)

摘要:给定一个正整数n和一个图族F。Kn的边染色中使得Kn不含有F中任意一个图的多色图的最大的颜色数为F的Anti-Ramsey数,记作AR(n,F)。本文给出了任意一条边都在三角形中的极小连通图的Anti-Ramsey数。

关键词:Anti-Ramsey数;边染色;双边-p-临界图;极小连通图

0　引言

Anti-Ramsey数最早由Erd¨os等[1]于20世纪70年代提出并进行了研究。Erd¨os等在Anti-Ramsey理论中,研究了Kn的不含polychromatic子图的边染色至多用多少种颜色,即固定n,求k(k是颜色数)。他们提出Anti-Ramsey数与Tur´an数非常接近,得出并证明了当n→∞时,

AR(n,H)−ex(n,H)=o(n2)

其中,H={H−e:e∈E(H)}。并利用关于Tur´an数渐进性的一个较早的结论,进而得到当n→∞时,

其中,d+1=m in{χ(H−e):e∈E(H)}。

Anti-Ramsey理论从提出到现在,经历了近40年的时间。在这期间,对于典型图,如圈、路、星、完全图等的Anti-Ramsey数都得到了相关结论,已基本解决。本文给出了任意一条边都在三角形中的极小连通图的Anti-Ramsey数。

1　基本符号及定义

本文中所出现的图均是非空、简单、无向、有限图,G⊆Kn。涉及的符号及说明见表1。

表1　图的相关符号Tab.1　The symbolof graph

定义1多色图:若存在Kn的一个边染色c,使得G的所有边都染不同颜色,则称G是边染色c下的多色(polychromatic或rainbow)图。

定义2F-free图:若G的任一子图都不属于图族F,则称G是F-free图。

定义3Anti-Ramsey数:Kn的所有F-free边染色中所用的最多的颜色数,记为AR(n,F)。图族F中只有一个图H时,AR(n,{H})=AR(n,H)。

定义4表示图:令c是Kn的AR(n,H)-边染色,若c中的每一种颜色在子图L中出现且仅出现一次,则子图L称为Kn在染色c下的表示图。

定义5双边-p-临界:对于任意的一个图族F,Ψ(F−)≥p,若∃H ∈F且e1,e2∈E(H)使得χ(H−e1−e2)=p,则称图族F是双边-p-临界的。其中F−={H−e:H∈F,e∈E(H)},Ψ(F−)是子色数,

Ψ(F−)=m in{χ(F):F∈F−}−1

定义6 j型:若对于每个n来说,j≥1都是[p]中使得Tnj,p是F-free的最大的数,则称双边-p-临界图F有j型。

Jiang等[2]研究了双边-p-临界图族F的Anti-Ramsey数。

2　引理

引理1[2]若Kn的一个t(n,p)+j-边染色c如下:H⊂Kn且H∼=Tnp,H是c下的rainbow图; E(Kn−H)染不同于E(H)的j种新颜色,使得H的每一部中的边都染相同颜色,且这j种新颜色中的任意一种至少出现在一部里,则c是F-free染色。

引理2[2]令正整数p≥2,对于任意一个双边-p-临界有j型的图族F,都存在一个正整数n0,使得对于所有的n,n≥n0,都有

AR(n,F)=t(n,p)+j

成立,并且,Kn的所有达到这个界的F-free边染色都是引理1中所描述的边染色。

引理3[3]对于正整数n,k,若n≥k≥4,则有

rb(n,Kk)=ex(n,Kk−1)+2

引理4[4]给定一个正整数n和一个图H,有

ex(n,H)≤AR(n,H)≤ex(n,H)

其中,H={H−e:e∈E(H)}。

3　主要结果

构造1令k是一个正整数,且k≥4。下面构造k阶图Gk3:

当k是偶数时,

(1)Gk3只有一个k−1-度点;

(2)Gk3只有一个3-度点;

(3)其余点均为2-度点。

当k是奇数时,

(1)Gk3只有一个k−1-度点;

(2)其余点均为2-度点。

本文证明了Gk3是任意一条边都在三角形中的连通图的一个极小图,并给出了图G53的Anti-Ramsey数。

定理1 Hk={H:H是一个k阶连通图,且H的任意一条边都在三角形中},则对于所有的正整数k≥4,Gk3是Hk的一个极小图。

证明当k是偶数时,对k用归纳法证明。当k=4时,结论显然成立。假设对于大于4小于k的偶数,结论均成立。下面,证明结论对于k也成立。

由构造1可知,Gk3至少有两个相邻2-度点,设为u,v。因此,Gk3−u−v只有一个k−3-度点和一个3-度点,其余均为2-度点。根据假设,Gk3−u−v 是Hk−2的一个极小图,显然

e(Gk3)=e(Gk3−u−v)+3

若任意的H∈Hk,则有

e(Gk3)≥e(Gk3−u−v)+3

根据归纳假设,结论成立。

当k是奇数时,同理可证。

定理2若正整数n,n≥5,则G53是一个双边-2-临界有Type1的图,

AR(n,G53)=t(n,2)+1

并且,Kn的所有达到这个界的G53-free边染色都是引理1中所描述的边染色。

证明定义

G−={G53−e:e∈G53}

则有ψ(G−)=2,且存在两条边e1,e2∈E(G53),使得

χ(G53−e1−e2)=2

即G53是一个双边-2-临界图。显然,G53有1型。因此,由引理1得

AR(n,G53)≥t(n,2)+1

由引理2,存在正整数n0,使得对于所有的n, n≥n0,都有

AR(n,G53)=t(n,2)+1

接下来,我们对n运用归纳法证明当5≤n≤n0时,

AR(n,G53)≤t(n,2)+1

若n=5,令V(K5)={u,v,w,x,y}。我们来用反证法证明在E(K5)的任意一个G53-free染色中至多有7种颜色。假设AR(5,G53)≥8,令c是E(K5)的一个8-染色,图L是表示图。因为q(K5)=10, q(L)=8,显然,可以去掉完全图K5的两条边得到图L。只需考虑两种去边的方法:①去掉一个2K2; ② 去掉一个P3。但是,无论用哪种方法去边,结果图L都含有G53的一个copy。所以,

AR(5,G53)≤7

结论成立。下面,假设对于所有大于5,且小于n的正整数,结论均成立。现在只需证明结论对于n也成立。

令c1是E(Kn)的任意一个G53-free AR(n,G53)-染色。如果Kn在染色c1下不含有K4的rainbow copy,则由引理3、引理4可知AR(n,G53)≤t(n,2)+1。如果Kn在染色c1下含有K4的rainbow copy H,令T=V(Kn)V(H)。显然c1是E(Kn−4)的一个G53-free染色(否则,若Kn−4含有G53的rainbow copy,则Kn必含有G53的rainbow copy,与c1是E(Kn)的G53-free染色矛盾)。由归纳假设,有

AR(n−4,G53)≤t(n−4,2)+1

我们断定E(H,T)中与KT的同一顶点相关联的边(定义E(H,T))至多有一种不同于E(H)和E(KT)上的颜色。否则,若c(1),c(2)是两种不同于E(H) 和E(KT)上的颜色,不妨分别设c(u1v)=c(1), c(u2v)=c(2),其中v∈V(KT),u1,u2∈V(H),则H+vu1+vu2为G53的rainbow copy,矛盾。因此,

AR(n,G53)≤AR(n−4,G53)+6+(n−4)≤

t(n−4,2)+1+6+(n−4)≤

t(n,2)+1(因为n≥6)

综上,可得

AR(n,G53)=t(n,2)+1

证毕。

参考文献:

[1]ERD¨OSP,SIMONOVITSM,S’OSV T.Anti-Ram sey theorems[J].Graphsand Combinatorics,1985,1(1):23-28.

[2]JIANG T,PIKHURKO O.Anti-Ramsey numbers of doubly edge critical graphs[J].Graph Theory,2009,61(3): 210-218.

[3]SCHIERMEYER I.Rainbow numbers formatchings and complete graphs[J].Discrete Mathematics,2004,286(1-2):157-162.

[4]JIANG T.Anti-Ramsey numbers of subdivide graphs[J]. Combin Theory(B),2002,85(2):361-366.

中图分类号:O157.5

文献标志码:A

文章编号:1001-4543(2015)01-0060-03

收稿日期:2015-01-05

通讯作者:段春燕(1984–),女,河北保定人,讲师,硕士,主要研究方向为图论及其应用、组合数学。电子邮箱duanchunyan339@126.com。

Anti-Ram sey Number of a Minimal Graphs

DUAN Chun-yan1,M IAO Lian-ying2
(1.Chutian College,Huazhong Agricultural University,Wuhan 430205,P.R.China;2.Schoolof Science,China University ofM ining and Technology,Xuzhou 221008,Jiangsu,P.R.China)

Abstract:For given a positive integer n and a family F of graphs,theanti-Ramsey number AR(n,F)denotes themaximum number of colors in an edge-coloring of Knsuch that no subgraph of Knbelonging to F has distinct colors on its edges.The Anti-Ramsey numbersof a special classofgraphsaregiven.

Keywords:Anti-Ramsey number;edge-coloring;doubly edge-p-criticalgraph;m inimalgraph