Flower snark圖的強邊染色

董曉媛

(南通師范高等專科學校數(shù)理系，江蘇南通 226007)

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

Snark圖是源自3-邊著色猜想而構造的圖，若圖是二邊連通的3正則圖且不可3-邊著色，同時圍長至少為5，也無非平凡3-邊割集，則稱為snark.Petersen圖是最小的snark.本文對Flower snark圖的強邊染色進行了研究.下面給出Flower snark圖的定義.

定義1Gn是一個簡單的非平凡的連通的三正則圖，點集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}，點的標號對n取模，Hn可以由Gn通過用邊bn-1c0、cn-1b0替換bn-1b0、cn-1c0得到.如果n為奇數(shù)且n≥5，Hn被稱為Flower snark圖，其他的圖被稱為Flower snark圖的相關圖.

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

由定義1，給出F5的一個畫法，如圖2所示.

a與a相連，b與b相連，c與c相連圖1 Fn的一個畫法

圖2 Flower snark圖F5的一個畫法

圖圖示

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

證明 首先給出F5的一個強邊染色，如圖4所示.

圖4 F5的一個強邊染色

圖的一個強邊染色

證明 首先給出F6的一個強邊染色，如圖6所示.

圖6 F6的一個強邊染色

圖的另一個強邊染色

證明 首先給出F7的一個強邊染色，如圖8所示.

圖8 F7的一個強邊染色

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

圖9 H圖示

證明 假設圖H可以用5色強邊染色.如圖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.不妨設f(e4)=d，則f(e5)=e，則e6只能染d,e中的一個.

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

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

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

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

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

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

(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，此時e10不能用a,b,c,d,e五種顏色染色.產(chǎn)生矛盾.

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

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

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

(ⅱ)若f(e9)=c，則f(e10)≠b,c,d,e，此時f(e10)=a，此時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.此時f(e10)≠b,c,d,e，此時f(e10)=a，此時e11只能染e.

②若f(e8)=d，則f(e9)≠b,c,d,e，所以f(e9)=a.此時f(e10)≠a,c,d,e，則f(e10)=b，此時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，此時e10不能用a,b,c,d,e五種顏色染色.產(chǎn)生矛盾.

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

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

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

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