董曉媛

(南通師范高等?？茖W(xué)校數(shù)理系，江蘇南通 226007)

圖G的一個(gè)正常k-邊染色是用k種顏色對(duì)圖G的邊集進(jìn)行染色，使得任意相鄰的邊染不同的顏色.設(shè)π是圖G的一個(gè)正常k-邊染色，如果染色π使得圖G中有公共邊的任意兩條邊的染色也不相同，則稱π是圖G的一個(gè)k-強(qiáng)邊染色.強(qiáng)邊染色在無(wú)線電通訊網(wǎng)絡(luò)的無(wú)沖突信道分配問(wèn)題上具有重要的理論和實(shí)際意義.

Snark圖是源自3-邊著色猜想而構(gòu)造的圖，若圖是二邊連通的3正則圖且不可3-邊著色，同時(shí)圍長(zhǎng)至少為5，也無(wú)非平凡3-邊割集，則稱為snark.Petersen圖是最小的snark.本文對(duì)Flower snark圖的強(qiáng)邊染色進(jìn)行了研究.下面給出Flower snark圖的定義.

定義1Gn是一個(gè)簡(jiǎn)單的非平凡的連通的三正則圖，點(diǎn)集V(G)={ai,bi,ci,di:0≤i≤n-1}，邊集E(G)={aiai+1,bibi+1,cici+1,diai,dibi,dici:0≤i≤n-1}，點(diǎn)的標(biāo)號(hào)對(duì)n取模，Hn可以由Gn通過(guò)用邊bn-1c0、cn-1b0替換bn-1b0、cn-1c0得到.如果n為奇數(shù)且n≥5，Hn被稱為Flower snark圖，其他的圖被稱為Flower snark圖的相關(guān)圖.

把這些圖統(tǒng)一用Fn來(lái)表示，如圖1所示.

由定義1，給出F5的一個(gè)畫(huà)法，如圖2所示.

a與a相連，b與b相連，c與c相連圖1 Fn的一個(gè)畫(huà)法

圖2 Flower snark圖F5的一個(gè)畫(huà)法

圖圖示

當(dāng)n≥5時(shí)，為了研究Fn的強(qiáng)邊色數(shù)，將n分成n=3m+5、n=3m+6、n=3m+7(m為非負(fù)整數(shù))三類.

證明 首先給出F5的一個(gè)強(qiáng)邊染色，如圖4所示.

圖4 F5的一個(gè)強(qiáng)邊染色

圖的一個(gè)強(qiáng)邊染色

證明 首先給出F6的一個(gè)強(qiáng)邊染色，如圖6所示.

圖6 F6的一個(gè)強(qiáng)邊染色

圖的另一個(gè)強(qiáng)邊染色

證明 首先給出F7的一個(gè)強(qiáng)邊染色，如圖8所示.

圖8 F7的一個(gè)強(qiáng)邊染色

由引理2、引理3和引理4得到如下結(jié)論.

圖9 H圖示

證明 假設(shè)圖H可以用5色強(qiáng)邊染色.如圖9所示，邊e1,e2,e3,e4,e5的距離都小于等于3，不能染同一種顏色，這5種顏色不妨記作a,b,c,d,e，令f(e1)=a,f(e2)=b,f(e3)=c，則e4,e5只能染d,e.不妨設(shè)f(e4)=d，則f(e5)=e，則e6只能染d,e中的一個(gè).

情形一：若f(e6)=d，則f(e7)≠a,d，則e7只能染b,c,e中的一個(gè).

(1)若f(e7)=b，則f(e8)≠a,b,d,e，則e8只能染c.此時(shí)e9不能用a,b,c,d,e五種顏色染色.產(chǎn)生矛盾.

(2)若f(e7)=c，則f(e8)≠a,c,d,e，則e8只能染b.此時(shí)e9不能用b,c,d,e染色，所以f(e9)=a，此時(shí)e10不能用a,b,c,d,e五種顏色染色.產(chǎn)生矛盾.

(3)若f(e7)=e，則f(e8)≠a,d,e，則e8只能染b,c.

①若f(e8)=b，則f(e9)≠b,d,e，所以f(e9)=a,c.

(ⅰ)若f(e9)=a，則f(e10)≠a,b,c,d,e，此時(shí)e10不能用a,b,c,d,e五種顏色染色.產(chǎn)生矛盾.

(ⅱ)若f(e9)=c，則f(e10)≠a,b,d,e，此時(shí)f(e10)=a，此時(shí)e11只能染d或者e.

②若f(e8)=c，則f(e9)≠b,c,d,e，所以f(e9)=a.則f(e10)≠a,c,d,e，此時(shí)f(e10)=b，此時(shí)e11只能染d或者e.

情形二：若f(e6)=e，則f(e7)≠a,e，則e7只能染b,c,d中的一個(gè).

(1)若f(e7)=b，則f(e8)≠a,b,e，則e8只能染c,d.

①若f(e8)=c，則f(e9)≠b,c,e，所以f(e9)=a,d.

(ⅰ)若f(e9)=a，則f(e10)≠a,b,c,d,e，此時(shí)e10不能用a,b,c,d,e五種顏色染色.產(chǎn)生矛盾.

(ⅱ)若f(e9)=d，則f(e10)≠b,c,d,e，此時(shí)f(e10)=a，此時(shí)e11只能染e.

②若f(e8)=d，則f(e9)≠b,d,e，所以f(e9)=a,c.

(ⅰ)若f(e9)=a，則f(e10)≠a,b,d,e，此時(shí)f(e10)=c，此時(shí)e11只能染e.

(ⅱ)若f(e9)=c，則f(e10)≠b,c,d,e，此時(shí)f(e10)=a，此時(shí)e11只能染e.

(2)若f(e7)=c，則f(e8)≠a,c,e，則e8只能染b,d.

①若f(e8)=b，則f(e9)≠a,b,c,e，所以f(e9)=d.此時(shí)f(e10)≠b,c,d,e，此時(shí)f(e10)=a，此時(shí)e11只能染e.

②若f(e8)=d，則f(e9)≠b,c,d,e，所以f(e9)=a.此時(shí)f(e10)≠a,c,d,e，則f(e10)=b，此時(shí)e11只能染e.

(3)若f(e7)=d，則f(e8)≠a,d,e，則e8只能染b,c.

①若f(e8)=b，則f(e9)≠b,d,e，所以f(e9)=a,c.

(ⅰ)若f(e9)=a，則f(e10)≠a,b,c,d,e，此時(shí)e10不能用a,b,c,d,e五種顏色染色.產(chǎn)生矛盾.

(ⅱ)若f(e9)=c，則f(e10)≠b,c,d,e，此時(shí)f(e10)=a，此時(shí)e11只能染d或者e.

②若f(e8)=c，則f(e9)≠b,c,d,e，所以f(e9)=a.此時(shí)e10不能用a,b,c,d,e五種顏色染色.產(chǎn)生矛盾.

我們發(fā)現(xiàn)，在討論了圖H中兩個(gè)塊后，e11只能染d或者e.把兩個(gè)塊推廣到6個(gè)塊，會(huì)發(fā)現(xiàn)在e11所在的長(zhǎng)為3的路上只能染d或者e，與定義矛盾.

由定理1和定理2，得到定理3.