丁吉麗,邊 紅*，于海征

(1.新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，新疆 烏魯木齊 830017;2.新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆 烏魯木齊 830046)

1 預(yù)備知識

圖的anti-Ramsey數(shù)是由Erd?s等[1]在1973年提出的.若將圖G的邊染色中所有的邊都染成不同的顏色，則稱圖G是彩虹的.圖G的anti-Ramsey數(shù)ar(G，H)是指圖G的邊染色中所用的最大顏色數(shù)，使得圖G不包含彩虹子圖H[1].Erd?s等[1]最初研究anti-Ramsey數(shù)的母圖是完全圖，且對完全圖中的圈和路的anti-Ramsey數(shù)提出猜想，并闡明了圖的anti-Ramsey數(shù)和圖的Turn數(shù)之間有著密切的聯(lián)系.圖H的Turn數(shù)ex(n，H)是指n個(gè)頂點(diǎn)的圖中所包含的最大邊數(shù)，使得該圖不包含同構(gòu)于H的子圖[2].

沿著這條研究主線，學(xué)者們研究了完全圖中的其他圖類的anti-Ramsey數(shù)，比如：樹[3]、小的二部圖[4]、點(diǎn)不交的圈[5]、匹配[6-8]等.后來，研究anti- Ramsey問題的母圖從完全圖變換成其他的圖類，比如完全二部圖[9-11]、完全分裂圖[12]、超立方體[13]、平面三角剖分圖[14]、超圖[15]等.

在圖G中，對于?v∈V(G)，?e∈E(G).用C(G)表示圖G所有邊的顏色的集合；C(v)表示與頂點(diǎn)v相關(guān)聯(lián)的邊的顏色的集合，c(e)表示邊e的顏色.G1和G2是圖G中兩個(gè)不同的子圖，E(G1，G2)表示一個(gè)端點(diǎn)在G1中，另一個(gè)端點(diǎn)在G2中的所有邊的集合,C(G1,G2)表示E(G1，G2)中所有邊的顏色的集合.

2 主要結(jié)果

2.1 聯(lián)圖的anti-Ramsey數(shù)

因?yàn)镃3=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是一個(gè)單色圖.

下面根據(jù)n的奇偶進(jìn)行分類討論：

情形1n是奇數(shù).

情形2n是偶數(shù).

若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 聯(lián)圖的anti-Ramsey數(shù)

引理1[14]若Ck是邊著色圖G中的一個(gè)彩虹圈且k≥4,如果G[Ck]有一條弦，則在G中有一個(gè)長度小于k的彩虹圈.

彩虹的C3的位置有兩種，如圖1所示.

圖中C3的兩種位置Fig.1 Two location of C3 in

情形1彩虹C3位于前一種位置(圖1(a)).

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

2.3 聯(lián)圖的anti-Ramsey數(shù)

圖中C4的3種位置Fig.2 Three location of C4 in

2.4 聯(lián)圖的anti-Ramsey數(shù)

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

證明對于友誼圖Fn，實(shí)質(zhì)上是n個(gè)三角形有一個(gè)公共頂點(diǎn)的圖.按照這樣的特性，用n種顏色將每個(gè)三角形中和公共頂點(diǎn)關(guān)聯(lián)的兩條邊染成一樣的顏 色，剩余的n條邊用新的n種不同的顏色染色，此時(shí)在Fn中一定不含彩虹的C3.因此,ar(Fn，C3)≥2n.

如果用2n+1種顏色對Fn的邊任意染色，根據(jù)鴿巢原理，那么至少有一個(gè)三角形的3條邊顏色不一樣，即找到一個(gè)彩虹的C3.因此，ar(Fn，C3)<2n+1.