朱緒鼎， 鐘亞玲

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

0 引 言

如果一個(gè)偶長(zhǎng)度的序列x1x2…x2l的前一半和后一半是一樣的,即對(duì)任意的1≤i≤l,xi=xi+l,那么就稱該序列為一個(gè)重復(fù).如果一個(gè)序列不含有重復(fù)的子序列,那么就稱該序列為一個(gè)無重復(fù)的序列.1906年，Thue[1]證明了僅用3個(gè)符號(hào)可以寫出一個(gè)無限長(zhǎng)的無重復(fù)序列.Thue的這個(gè)結(jié)果在數(shù)學(xué)的很多分支中有重要的影響,它催生了一個(gè)新的學(xué)科：符號(hào)動(dòng)力學(xué).Thue定理及其推廣在數(shù)學(xué)和計(jì)算機(jī)科學(xué)的不同領(lǐng)域中有許多重要的應(yīng)用.

2002年，Alon等[2]將無重復(fù)序列的概念和圖的染色結(jié)合起來,提出了圖的無重復(fù)染色的概念.圖G的一個(gè)頂點(diǎn)染色c是無重復(fù)的是指圖G中的任何一條簡(jiǎn)單路v1v2…v2l的顏色序列c(v1)c(v2)…c(v2l)不是一個(gè)重復(fù).稱一個(gè)無重復(fù)染色所需要的最少顏色數(shù)為圖G的Thue染色數(shù)，記為π(G),即

π(G)=min{n:圖G存在一個(gè)無重復(fù)的n-染色}.

根據(jù)π(G) 的定義,Thue的結(jié)果等價(jià)于π(P∞)=3.

圖的無重復(fù)染色數(shù)在文獻(xiàn)[2-6]中已有大量的研究,得到了許多類圖的無重復(fù)染色數(shù)的上下界.特別是在文獻(xiàn)[4]中,Currie確定了所有圈圖的無重復(fù)染色數(shù).

定理1[4]設(shè)Cn是頂點(diǎn)數(shù)n≥3的圈圖.若n=5,7,9,10,14,17,則π(Cn)=4;否則π(Cn)=3.

下面給出圖G的無重復(fù)分?jǐn)?shù)染色的定義.

根據(jù)πf(G)的定義,對(duì)任意的圖G,πf(G)≤π(G).一個(gè)很自然的問題是:哪些圖G滿足πf(G)=π(G)?如果πf(G)≠π(G),那么π(G)-πf(G)的差值有多大?筆者已另文(待發(fā)表)證明了,若圖G是一條路或者是一棵沒有2度點(diǎn)的樹,則πf(G)=π(G)；同時(shí)還構(gòu)造了一個(gè)樹圖T,它的無重復(fù)分?jǐn)?shù)染色數(shù)是3.5,而它的無重復(fù)染色數(shù)是 4；對(duì)于圈圖的無重復(fù)分?jǐn)?shù)染色數(shù),得出除了n=10,14,17之外的所有n的πf(Cn)值.

對(duì)于圈圖Cn(n=10,14,17),πf(Cn)的研究更加困難.本文研究了這3個(gè)圈的無重復(fù)分?jǐn)?shù)染色數(shù)的上下界.

圖1 圈C10的一個(gè)無重復(fù)的2-重7-染色

1 圈C10

性質(zhì)1 若Y是X-rich,Z 是Y-rich,則X∩Z≠?;若XYZ∈T,YZW∈T,則W 是X-rich.

在接下來的討論中,若XYZ∈T,并且YZW∈T,則記XYZW∈Q.通過性質(zhì)1,若XYZW∈Q,則W是X-rich.

引理1 令P=(v1v2v3v4)是一條含有4個(gè)頂點(diǎn)的路.若c是P的一個(gè)無重復(fù)的k-重n-染色,則c(v1)∩c(v3)=?,或者c(v2)∩c(v4)=?.

引理2 假設(shè)P6=(v1v2…v6)是圈C10的一條路.若X1X2X3∈T,并且X4X5X6∈T, 則

1)X4,X5,X6分別是X2,X1,X3-rich;或者

2)X4,X5,X6分別是X1,X3,X2-rich.

情形1 X4∩X1=?.即X2X1X3X4∈Q,由此可以推導(dǎo)出X4是X2-rich.由X4∩X2≠?,通過引理1就能推導(dǎo)出X5∩X3= ?.現(xiàn)在可以根據(jù)X1X3X4X5∈Q, 推導(dǎo)出X5是X1-rich.根據(jù)X3X4X5X6∈Q, 推導(dǎo)出X6是X3-rich.故1)成立.

情形2 X4∩X2=?.因此,X1X2X3X4∈Q,可得X4是X1-rich.若X5∩X2= ?,則可由X2X4X5X6∈Q推導(dǎo)得到X6是X2-rich.同理,X3X2X4X5∈Q,推導(dǎo)得到X5是X3-rich.若X5∩X2≠?,則X6∩X3=?.否則,令a∈X1∩X4,b∈X2∩X5,c∈X3∩X6,在路v1v2v3v4v5v6上可以找到形如abcabc的一個(gè)重復(fù).因此,由X2X3X4X6∈Q推導(dǎo)出X6是X2-rich;由X3X4X6X5∈Q推導(dǎo)出X5是X3-rich.綜上所述,得2)成立.

情形3 X4∩X1≠?,X4∩X2≠?.由引理1知,X5∩X3= ?.因此,可以根據(jù)X3X4X5X6∈Q推導(dǎo)出X6是X3-rich.這樣就有X5∩X2=?.否則,令a∈X1∩X4,b∈X2∩X5,c∈X3∩X6,可以在路v1v2v3v4v5v6上找到形如abcabc 的一個(gè)重復(fù).此時(shí)就可以根據(jù)X1X2X3X5∈Q推導(dǎo)出X5是X1-rich,同時(shí)由X2X3X5X4∈Q推導(dǎo)出X4是X2-rich.因此，1)成立.引理2證畢.

引理3 不可能有X1X2X3∈T, X4X5X6∈T, X7X8X9∈T.

證明 反正法.假設(shè)X1X2X3∈T, X4X5X6∈T, X7X8X9∈T. 根據(jù)引理2和對(duì)稱性,對(duì)于顏色序列X1X2X3X4X5X6,可以假設(shè)X4,X5,X6分別是X2,X1,X3-rich.

同樣,對(duì)于顏色序列X4X5X6X7X8X9,應(yīng)用引理2.若引理2的1)成立,即X7,X8,X9分別是X5,X4,X6-rich,則X7∩X1≠?(因?yàn)閄7和X1都是X5-rich).同理,X8∩X2≠?,X9∩X3≠?.接下來證明

X10∩X4=?,X10∩X6=?.

若不然,則令a∈X1∩X7,b∈X2∩X8,c∈X3∩X9,d∈X10∩X4,或者a∈X1∩X7,b∈X2∩X8,c∈X3∩X9,d∈X10∩X6.因此，可在路v7v8v9v10v1v2v3v4上找到形如abcdabcd的一個(gè)重復(fù),或者可在路v6v7v8v9v10v1v2v3上找到形如dabcdabc的一個(gè)重復(fù).

推論1 若X1X2X3∈T, 且X4∩X6≠?,則X2∩X4≠?.

證明 反正法.假設(shè)X2∩X4=?,則X2X3X4∈T, X5X6X7∈T. 根據(jù)引理3得X8∩X10≠?,X9∩X1≠?,故可令a∈X8∩X10,b∈X9∩X1,從而可以在路v8v9v10v1上找到形如abab的一個(gè)無重復(fù).得到矛盾.推論1證畢.

引理4 存在一個(gè)整數(shù)i,使得對(duì)j=0,1,2,3,4,Xi+2j∩Xi+2j+2≠?.這里的下標(biāo)運(yùn)算是模10 加法.

證明 設(shè)i∈{1,2,…,10},令Ti=max{k:Xi+2j∩Xi+2j+2≠?, j=1,2,…,k}.這里的下標(biāo)運(yùn)算是模10 加法.顯然,對(duì)任意的i,Ti≤4.令T=max{Ti:1≤i≤4}.

若T=0,不妨設(shè)T1=T=0,則X1∩X3≠?,X3∩X5=?,X9∩X1=?.同時(shí)由引理1知,X2∩X4=?.那么就有X10X1X2∈T, X3X4X5∈T, 通過引理3得,X6∩X8≠?.由引理1得,X5∩X7=?.故X2X3X4∈T,X5X6X7∈T.同樣,根據(jù)引理3,有X8∩X10≠?,即與T=0矛盾.

若T=1,不妨設(shè)T1=T=1,則X1∩X3≠?,X3∩X5≠?,X5∩X7=?,X9∩X1=?.那么就有X9X10X1∈T, X2X3X4∈T, X5X6X7∈T, 與引理3矛盾.

若T=2,不妨設(shè)T1=T=2,則X1∩X3≠?,X3∩X5≠?,X5∩X7≠?,X7∩X9=?.那么就有X4X5X6∈T,X7X8X9∈T,根據(jù)引理3,就有X10∩X2≠?.此時(shí)可令a∈X10∩X2,b∈X1∩X3,則在路v10v1v2v3上存在形如abab的一個(gè)重復(fù).矛盾.

若T=3,不妨設(shè)T1=T=3,則X1∩X3≠?,X3∩X5≠?,X5∩X7≠?,X7∩X9≠?,X9∩X1=?.那么就有X6X7X8∈T, X9X10X1∈T, 根據(jù)引理3,有X2∩X4≠?.此時(shí)可令a∈X2∩X4,b∈X3∩X5,則在路v2v3v4v5上存在形如abab的一個(gè)重復(fù).矛盾.

綜上可得T=4.引理4證畢.

在以下的討論中,不妨假設(shè)X1∩X3,X3∩X5,X5∩X7,X7∩X9,X9∩X1都是非空的.根據(jù)引理1得,X2X3X4,X4X5X6,X6X7X8,X8X9X10,X10X1X2∈T.

引理5 對(duì)任意的i,若Xi∩Xi+3=?,則Xi∩Xi-3≠?.

證明 根據(jù)i的奇偶性,分2種情形討論.

情形1 i是偶數(shù).根據(jù)對(duì)稱性,不妨設(shè)i=6.假設(shè)X6∩X3=?,且X6∩X9=?.因此,X2X3X4X6∈Q?X6是X2-rich,X10X8X9X6∈Q?X6是X10-rich.則X10∩X2≠?.故可令a∈X10∩X2,b∈X1∩X3,從而在路v10v1v2v3上存在形如abab的一個(gè)重復(fù).矛盾.

情形2 i是奇數(shù).根據(jù)對(duì)稱性,不妨設(shè)i=3.假設(shè)X3∩X6=?,且X3∩X10=?.因此,X4X2X3X10∈Q?X10是X4-rich,X1X2X10X3∈Q?X3是X1-rich,X5X4X6X3∈Q?X3是X5-rich,X2X3X4X6∈Q?X6是X2-rich.

若X3∩X9≠?,則可令a∈X9∩X3,b∈X10∩X4,c∈X1∩X5,d∈X2∩X6.因此,在路v9v10v1v2v3v4v5v6上存在形如abcdabcd的一個(gè)重復(fù).所以X3∩X9=?.

若X3∩X7≠?,則可令a∈X3∩X7,b∈X10∩X4,c∈X1∩X5,d∈X2∩X6.因此,在路v10v1v2v3v4v5v6v7上存在形如bcdabcda的一個(gè)重復(fù).所以X3∩X7=?.

綜上可得X8X9X10X3∈Q, 所以X3是X8-rich.

則

綜上所述,X1,X5,X8都是X3-rich,X10和X7都是X4-rich,X6和X9都是X2-rich,這樣可以推導(dǎo)出X10∩X7,X9∩X6,X8∩X5都非空.

現(xiàn)令a∈X10∩X7,b∈X9∩X6,c∈X8∩X5,在路v10v9v8v7v6v5上存在形如abcabc的一個(gè)重復(fù).矛盾.引理5證畢.

引理6 不存在i,使得Xi∩Xi+3≠?,且Xi+1∩Xi+4≠?.

證明 假設(shè)存在i,不妨設(shè)i=1,使得X1∩X4≠?,且X2∩X5≠?.接下來證明X10∩X3=?,且X3∩X6=?.若不然,令a∈X10∩X3,b∈X1∩X4,c∈X2∩X5,或者令a∈X1∩X4,b∈X2∩X5,c∈X3∩X6.則在路v10v1v2v3v4v5上存在形如abcabc的一個(gè)重復(fù),或者在路v1v2v3v4v5v6上存在形如abcabc的一個(gè)重復(fù).矛盾.故存在i,使得Xi∩Xi-3=?,且Xi∩Xi+3=?.與引理5矛盾.引理6證畢.

引理7 不存在i,使得Xi∩Xi+3=?,且Xi+1∩Xi+4=?.

證明 假設(shè)存在i,使得Xi∩Xi+3=?,且Xi+1∩Xi+4=?.根據(jù)引理5,Xi∩Xi-3≠?,Xi+1∩Xi-2≠?,與引理6矛盾.引理7證畢.

由引理6和引理7,可再分2種情形進(jìn)行討論.

情形1 設(shè)X1∩X4,X3∩X6,X5∩X8,X7∩X10,X9∩X2都非空,則X2∩X5,X4∩X7,X6∩X9,X8∩X1,X10∩X3都是空集.這樣推導(dǎo)出X2X4X5X6,X4X6X7X8,X3X2X4X5,X5X4X6X7,X7X6X8X9∈Q ,則X2∩X6,X3∩X7,X4∩X8,X5∩X9都非空.令a∈X2∩X6,b∈X3∩X7,c∈X4∩X8,d∈X5∩X9,則在路v2v3v4v5v6v7v8v9上存在形如abcdabcd 的一個(gè)重復(fù).矛盾.

情形2 設(shè)X1∩X4,X3∩X6,X5∩X8,X7∩X10,X9∩X2都是空集,則X2∩X5,X4∩X7,X6∩X9,X8∩X1,X10∩X3都是非空.這樣就推導(dǎo)出X10X2X1X4∈Q,X4X5X6X8∈Q,即X10和X8都是X4-rich,也就是X10∩X8≠?.令a∈X8∩X10,b∈X9∩ X1,則在路v8v9v10v1上存在形如abab的一個(gè)重復(fù).矛盾.定理2證畢.

2 圈C14,C17

隨著圈的長(zhǎng)度增加,研究難度更大,筆者將采取另外的方法進(jìn)行研究.

下面以X3,X4,X5,R 為參照,描述其他的顏色集Xj.令

Xj=(aj,bj,cj,rj)k,j=1,2,…,n,

則

aj≤1,bj≤1,cj≤1,rj≤ε,且aj+bj+cj+rj=1.

引理8 設(shè)P8=v1,v2,…,v8.若X3X4X5∈T, 則a6>ε和b6>ε不可能同時(shí)成立.

證明 反正法.假設(shè)a6>ε,b6>ε同時(shí)成立.因?yàn)橄噜彽念伾幌嘟?所以X6∩X5=?,即根據(jù)前面的描述有c6=0.因?yàn)閎6>ε,所以X6∩X4≠?.根據(jù)引理1,就有X7∩X5=?,即c7=0.

接下來證明a7>0,b7>0.因?yàn)閞7≤ε,a7+b7+c7+r7=1,所以a7,b7不可能同時(shí)為零.

假設(shè)a7=0,則 b7=1-a7-c7-r7≥1-ε.因?yàn)閎6+b7>1,所以X6∩X7≠?.矛盾.從而a7>0.同理可證b7>0.所以a7>0,b7>0.

下面證明c8=0,c2=0.若不然,則令a∈X3∩X6,b∈X4∩X7,c∈X5∩X8.因此,在路v3v4v5v6v7v8上就可找到一個(gè)重復(fù)abcabc;或者令a∈X3∩X6,b∈X4∩X7,c∈X5∩X2,在路v2v3v4v5v6v7上同樣可以找到一個(gè)重復(fù)cabcab.

因?yàn)閄3∩X2= ?,所以a2=0.通過計(jì)算得b2=1-a2-c2-r2=1-r2≥1-ε.此時(shí)X2∩X4≠?,b2+b6>1.根據(jù)引理1,X1∩X3=?,即a1=0.因r1+r2≤ε,b1≤1- b2= r2,故c1=1-a1-b1-r1=1-b1-r1≥1-(r1+r2)≥1-ε>0,即X1∩X5≠?.

下面證明b8=0.若不然,則令a ∈X1∩X5,b∈X2∩X6,c∈X3∩X7,d∈X4∩X8.因此,可以在路v1v2v3v4v5v6v7v8上找到一個(gè)重復(fù)abcdabcd.綜上所述,a8=1-r8.因?yàn)閍7+a8≤1,所以a7≤1-a8=r8.故b7=1-a7-c7-r7=1-a7-r7≥1-r8-r7≥1-ε.因?yàn)閎6>ε,所以b7+b6>1,即X6∩X7≠?.矛盾.引理8證畢.

引理9 設(shè)P8=v1,v2,…,v8.若X3X4X5∈T, 則

1)|X6∩X3|≥(1-2ε)k,且X4X5X6∈T; 或者

2)|X6∩X3|≥(1-2ε)k,|X7∩X4|≥(1-2ε)k,且X5X6X7∈T; 或者

3)|X6∩X4|≥(1-2ε)k,|X7∩X3|≥(1-2ε)k,且X5X6X7∈T.

證明 根據(jù)引理8,考慮下面2種情形：

情形1 b6≤ε.由X6∩X5=?知c6=0,從而得a6=1-b6-r6≥1-2ε(即|X6∩X3|≥(1-2ε)k ).接下來再分2種情形討論.

①X6∩X4=?.因?yàn)閄4∩X5=?,X5∩X6=?,所以X4X5X6∈T.因此,1)成立.

②X6∩X4≠?.由引理1知,X7∩X5=?,即c7=0,X5X6X7∈T.因?yàn)閍7+a6≤1,b6=1-a6-c6-r6,所以a7≤b6+r6.又因?yàn)閞6+r7≤ε,所以b7=1-a7-r7≥1-(b6+r6+r7)≥1-2ε.因此,2)成立.

情形2 a6≤ε.因?yàn)閄6∩X5=?,所以c6=0,因而b6=1-a6-r6≥1-2ε.由X6∩X4≠?和引理1知,X7∩X5=?,即c7=0,X5X6X7∈T.

因?yàn)閎7+b6≤1,所以b7≤1-b6=1-(1-a6-r6)= a6+r6.經(jīng)計(jì)算得a7=1-b7-r7≥1-(a6+r6+r7)≥1-2ε.因此,3)成立.引理9證畢.

定義2 設(shè)φ:{v1,v2,…,vn}→{A,B,C}是路Pn的一個(gè)標(biāo)號(hào).若存在i, j(i

證明 不妨設(shè)X3X4X5∈T, 構(gòu)造標(biāo)號(hào)φ:{v1,v2,…,vn}→{A,B,C}.令φ(v3)=A,φ(v4)=B,φ(v5)=C.假設(shè)φ(vi),φ(vi+1),φ(vi+2)已定義,且c(vi)c(vi+1)c(vi+2)∈T. 根據(jù)引理9,下面三者之一成立:

1)|c(vi+3)∩c(vi)|≥(1-2ε)k,且c(vi+1)c(vi+2)c(vi+3)∈T;

2)|c(vi+3)∩c(vi)|≥(1-2ε)k,|c(vi+4)∩c(vi+1)|≥(1-2ε)k,且c(vi+2)c(vi+3)c(vi+4)∈T;

3)|c(vi+3)∩c(vi+1)|≥(1-2ε)k,|c(vi+4)∩c(vi)|≥(1-2ε)k,且c(vi+2)c(vi+3)c(vi+4)∈T.

若1)成立,則令φ(vi+3)=φ(vi);若2)成立,則令φ(vi+3)=φ(vi),φ(vi+4)=φ(vi+1);若3)成立,則令φ(vi+3)=φ(vi+1),φ(vi+4)=φ(vi).依此類推,可根據(jù)定義給出所有頂點(diǎn)的標(biāo)號(hào).由定義2知,對(duì)任意的同色伙伴vi,vj,|c(vi)∩c(vj)|≥(1-2ε)k.引理10證畢.

根據(jù)引理10,相鄰的頂點(diǎn)所給的符號(hào)是不同的,所以對(duì)于頂點(diǎn)個(gè)數(shù)為4的路,同一個(gè)符號(hào)最多出現(xiàn)2 次;對(duì)于頂點(diǎn)個(gè)數(shù)分別為5和6的路,同一個(gè)符號(hào)最多出現(xiàn)3 次;對(duì)于頂點(diǎn)個(gè)數(shù)為7的路,同一個(gè)符號(hào)最多出現(xiàn)4 次;對(duì)于頂點(diǎn)個(gè)數(shù)為8的路,同一個(gè)符號(hào)也最多出現(xiàn)4 次,且這個(gè)符號(hào)必須標(biāo)在路的起始頂點(diǎn)上,即形如ABACABCA,否則就有ABACABAC 出現(xiàn).因此,對(duì)于頂點(diǎn)個(gè)數(shù)為9 的路,同一個(gè)符號(hào)也最多出現(xiàn)4 次;對(duì)于頂點(diǎn)個(gè)數(shù)依次為10,11,12 的路,同一個(gè)符號(hào)最多也只能出現(xiàn)5 次；對(duì)于頂點(diǎn)個(gè)數(shù)分別為13和14的路,同一個(gè)符號(hào)最多也只能出現(xiàn)6 次;對(duì)于頂點(diǎn)個(gè)數(shù)依次為15,16,17的路,同一個(gè)符號(hào)最多也只能出現(xiàn)7 次.

在圈C14上用3個(gè)符號(hào)進(jìn)行標(biāo)號(hào)時(shí),同一個(gè)符號(hào)最多出現(xiàn)6 次.不妨設(shè)這個(gè)符號(hào)為A,則第1個(gè)A與第6個(gè)A的交集為[1-6×( 2ε)]k>0.也就是說,對(duì)任意的i

在圈C17上用3個(gè)符號(hào)進(jìn)行標(biāo)號(hào)時(shí),同一個(gè)符號(hào)最多出現(xiàn)7 次.不妨設(shè)這個(gè)符號(hào)為A,則第1個(gè)A與第7個(gè)A 的交集為[1-7×(2ε)]k>0.也就是說,對(duì)任意的i

[1]Thue A.über unendliche Zahlenreihen[J].SelecTed MaThemaTical Papers of Axel Thue,1906(7):139-158.

[2]Alon N,GryTczuk J,Hauszczak M,eT al.NonrepeTiTive colorings of graphs[J].Random STrucTures & AlgoriThms,2002,21(3/4):336-346.

[3]Bre?ar B,GryTczuk J,Klav?ar S,eT al.NonrepeTiTive colorings of Trees[J].DiscreTe MaThemaTics,2007,307(2):163-172.

[4]Currie J D.There are Ternary circular square-free words of lengThnforn≥18[J].ElecTron J Combin,2002,9(1):N10.

[5]Kündgen A,Pelsmajer M J.NonrepeTiTive colorings of graphs of bounded Tree-widTh[J].DiscreTe MaThemaTics,2008,308(19):4473-4478.

[6]GryTczuk J.NonrepeTiTive colourings of graphs——A survey[J].InTernaTional Journal of MaThemaTics and MaThemaTical Sciences,2007,2007:74639.