段娟娟,丁　偉

(中國礦業(yè)大學(xué) 理學(xué)院,江蘇 徐州　221116)

0　引言

1　平面圖的無圈邊色數(shù)

引理1如果圖G是最大度為3的非正則的連通圖,則Xa′(G)≤4.

此定理的證明文[4]中已經(jīng)給出了證明,在此我們就不再敘述.

定理1設(shè)圖G是簡單圖,如果有g(shù)(G)≥4,則有Xa′(G)≤Δ(G)+4

定義1我們首先要了解圖的最大平均度的定義,在文[8]中定義了一個(gè)圖的最大平均度:

引理2如果圖G的Mad(G)<4,且δ(G)≥2,則圖G至少包含下面幾種情況之一.

情況1一個(gè)2度點(diǎn)至少鄰接一個(gè)度數(shù)小于等于4的點(diǎn);

情況2一個(gè)3度點(diǎn)至少鄰接一個(gè)小于等于4度的點(diǎn)和一個(gè)5度的點(diǎn);

情況3一個(gè)4度點(diǎn)至少鄰接一個(gè)2度點(diǎn);

情況4一個(gè)5度點(diǎn)至少鄰接一個(gè)2度點(diǎn)和一個(gè)3度點(diǎn);

情況5一個(gè)5度點(diǎn)至少鄰接4個(gè)3度點(diǎn);

情況6一個(gè)6度點(diǎn)至少鄰接鄰接5個(gè)3度點(diǎn),和一個(gè)度數(shù)小于等于Δ(G)-1;

情況7一個(gè)7度點(diǎn)鄰接7個(gè)3度點(diǎn);

情況8一個(gè)點(diǎn)x當(dāng)d(x)≥6時(shí),點(diǎn)x至少鄰接d(x)-3個(gè)2度點(diǎn)其中的一個(gè)可以是3度點(diǎn).

A) 如果x是2度點(diǎn)或3度點(diǎn)時(shí),則點(diǎn)x不轉(zhuǎn)移任何值給鄰接的點(diǎn);

證明假設(shè)圖G是不滿足定理成立的最小反例,設(shè)圖G是Δ(G)≥3,2-連通的圖,即圖G的δ(G)≥2.設(shè)k=Δ(G)+4,令l={1,2,3,…,k}是圖的顏色集合.由引理1知道圖G中至少包含上面的8中情況之一則我們分別來討論圖G的8種情況.

情況1設(shè)x是一個(gè)2度點(diǎn),鄰接一個(gè)4度點(diǎn)y,z是x的另外一個(gè)鄰點(diǎn).讓H=G-xy由圖G的最小性可知,C是圖H的一個(gè)無圈k染色,有Xa′(H)≤k.如果|C(x)∩C(y)|=0時(shí),對(duì)邊xy染顏色α∈l{C(x)∪C(y)},則可以得到圖G的一個(gè)無圈k染色.如果|C(x)∩C(y)|=1時(shí),|C(y)∪C(z)|=3+Δ-1=Δ+2,則對(duì)邊xy染顏色α滿足α∈l{C(y)∪C(z)},則可得到圖G的一個(gè)無圈邊染色.

情況2設(shè)x是一個(gè)3度點(diǎn),鄰接一個(gè)4度點(diǎn)y,一個(gè)5度點(diǎn)y1,z是x鄰接的另外一個(gè)點(diǎn)讓H=G-xy,則由圖G的最小性知,C是圖H的一個(gè)無圈k染色.在圖中設(shè)C(xz)=1,C(xy1)=2,如果|C(x)∩C(y)|=0時(shí),對(duì)邊xy染顏色α∈l{C(x)∪C(y)}則可以得到圖G的一個(gè)無圈k染色.如果|C(x)∩C(y)|=1時(shí),如果1∈C(y)時(shí),則有圖G|C(y)∪C(z)∪C(xy1)|≤Δ+3,則對(duì)邊xy染顏色α∈l{C(z)∪C(y)∪C(xy1)},α?C(z),2∈C(xy1)?C(y),則可以得到圖G的一個(gè)無圈k染色.如果2∈C(y)時(shí),則有圖G滿足|C(y)∪C(y1)∪C(xz)|≤Δ+3,則對(duì)邊xy染顏色α∈l{C(y)∪C(y1)∪C(xz)}且有α?C(y1),2∈C(xz)?C(y),則可得到圖G的一個(gè)無圈k染色.

如果|C(x)∩C(y)|=2時(shí),C(x)={1,2}∈C(y),若1=C(xz)?C(y1)則有圖G滿足,則對(duì)邊C(xy1)染顏色α∈l{C(y)∪C(y1)∪C(x)},則可以得到圖H的無圈k染色C′,此時(shí)有|C′(x)∩C′(y)|=|C(x)C(y)|=1則由上面的證明我們可以得到圖G的一個(gè)無圈k染色.若2=C(xy1)?C(z),既可以對(duì)邊xz重新染顏色α∈l{C(y)∪C(z)∪C(x)},則可以得到圖H的一個(gè)無圈k染色C″,有|C″(x)∩C″(y)|=|C(x)∩C(y)|=1,由上面的證明既可以得到圖G的無圈k染色.若有1=C(xz)∈C(y1),2=C(xy1)∈C(z)如果有C(z)∩C(y1)=C(y)∩C(z)=C(y)∩C(y1)={1,2}否則,可以對(duì)邊xy染顏色α滿足α∈l{C(y)∪C(z)∪C(y1)},可以得到圖G的一個(gè)無圈k染色.不是一般性我們可以假設(shè)C(y)={1,2,3},C(y1)={1,2,4,5,6},C(y)={1,2,7，…,k},則可以對(duì)邊xy1染顏色7,對(duì)邊xz染顏色3,則可得到圖H的一個(gè)無圈k染色C?,則得到|C?(x)∩C?(y)|<|C(x)∩C(y)|,根據(jù)上面的證明我們既可以得到圖G的一個(gè)無圈k染色.

情況3設(shè)x是一個(gè)4度點(diǎn),y是x鄰接的一個(gè)2度點(diǎn),yi(i=1,2,3)是x鄰接的其他度點(diǎn).設(shè)H=G-xy,由圖G的最小性可知,C是圖H的一個(gè)無圈k染色.不妨設(shè)C(xyi)=i,(i=1,2,3).如果|C(x)∩C(y)|=0時(shí),對(duì)邊xy染顏色α∈lC(x)∪C(y),即可得到圖G的一個(gè)無圈k染色.如果|C(x)∪C(y)|=1,不妨設(shè)C(xy1)=C(yu)=1,及可以對(duì)邊xy染顏色α∈lC(x)∪C(y1)∪C(y),因?yàn)閨C(x)∪C(y1)∪C(y)|≤Δ+2,我們既可以得到圖G的一個(gè)無圈k染色.

情況4設(shè)x是一個(gè)5度點(diǎn),則x鄰接的2度點(diǎn)設(shè)為y,u是y異于x的另外一個(gè)鄰點(diǎn).鄰接的3度點(diǎn)是y1,鄰接的其它度點(diǎn)是zi,(i=1,2,3),有圖G的最小性可以得到,可以得到圖H是一個(gè)無圈k染色,不是一般性可設(shè)C(xy1)=4,C(xzi)=i,(i=1,2,3).若果|C(x)∩C(y)|=0,則可以對(duì)邊xy染顏色α∈l{C(x)∪C(y)},及可以得到圖G的一個(gè)無圈k染色.如果|C(x)∩C(y)|=1,若C(yu)=4,則我們可以選擇α∈l{C(x)∪C(y)∪C(y1)}去染邊xy則可得到圖G的一個(gè)無圈k染色.不是一般性我們可以假設(shè)C(yu)=1,則可以對(duì)邊xy染顏色α∈l{C(x)∩C(y)∩C(z1)},因?yàn)槲覀冇蠧(x)∩C(y)∩C(z1)≤Δ+3即可以得到圖G的一個(gè)無圈k染色.

情況5設(shè)x是一個(gè)5度點(diǎn),則x鄰接的4個(gè)3度點(diǎn)分別是y,y1,y2,y3,其中ui,vi是點(diǎn)yi異于x的其它鄰點(diǎn),(i=1,2,3)z是x的另外一個(gè)鄰點(diǎn).讓H=G-xy,有圖G的最小性可以得到,可以得到圖H是一個(gè)無圈k染色,不失一般性,可以假設(shè)C(xz)=4,C(xyi)=i(i=1,2,3).如果|C(x)∩C(y)|=0,則可以對(duì)邊xy染顏色α∈l{C(x)∪C(y)},及可以得到圖G的一個(gè)無圈k染色.如果|C(x)∩C(y)|=1,不是一般性我們可以假設(shè)5∈C(y).若C(y)={1,5},則我們可以選擇α∈l{C(x)∪C(y)∪C(y1)}去染邊xy,則可得到圖G的一個(gè)無圈k染色.因?yàn)閨C(x)∪C(y)∪C(y1)|≤Δ+3.若C(y)≠{1,5},我們可以假設(shè)C(y)∩{1,2,3}=φ,因此C(y)={4,5}.如果顏色α∈{6,7,…,k}C(z),則可以對(duì)邊xy染顏色α即可得的圖G的一個(gè)無圈k染色.當(dāng){6,7,8，…,k}∈C(z),因?yàn)镃(xz)=4,以得到C(z)={4,6,7，…,k},d(z)=Δ.若存在某個(gè)yi,(i=1,2,3),有C(yi)≠5,我們既可以交換C(xz)與C(xyi)的顏色,得到圖H的一個(gè)無圈k染色C′,有|C′(x)∩C′(y)|=0,則有|C′(x)∩C′(y)|<|C(y)∩C(x)|=1,我們可以對(duì)邊xy染顏色α∈l{C′(x)∪C′(y)∪C′(yi)},既可以得到圖G的一個(gè)無圈k染色.若對(duì)所有的yi都有(i=1,2,3),C(yiui)=5,我們很容易得到存在β∈{6,7,…,k}有對(duì)所有的C(yivi)≠β,(i=1,2,3),則我們可以重新對(duì)邊xz染顏色1,對(duì)邊xy1染顏色β,既可以得到圖H的一個(gè)無圈k染色C″,有C″(x)∩C″(y)=φ,那么我們有上面的證明既可以得到圖G的一個(gè)無圈k染色.

情況6圖G包含一個(gè)6-點(diǎn)鄰接五個(gè)3--點(diǎn)和一個(gè)小于或等于(Δ-1)--點(diǎn).

設(shè)x是圖G的一個(gè)6-點(diǎn),它鄰接的五個(gè)3--點(diǎn)分別為v,v1,v2,v3,v4,其(Δ-1)--鄰點(diǎn)為y.設(shè)si,ti分別為頂點(diǎn)vi(i∈{1,2,3,4})的除x以外的兩個(gè)鄰點(diǎn),設(shè)G′=Gxv,則由圖G的最小性知G′存在一個(gè)k-無圈邊染色π.我們不妨設(shè)其染色為π(xv1)=1,π(xv2)=2,π(xv3)=3,π(xv4)=4,π(xy)=5,則:

(A) 如果|π(x)∩π(v)|=0,則我們可以從C{π(x),π(v)}中選取一種顏色染邊xv.從而得到圖G的一個(gè)k-無圈邊染色.

(B) 如果|π(x)∩π(v)|=1,我們不妨設(shè)6∈π(v),當(dāng)π(v)={1,6}時(shí),因?yàn)棣?G)≥6,從而|π(x)∪π(v)∪π(WG′(x,v))|≤8

如果存在一個(gè)頂點(diǎn)vi(i∈{1,2,3,4})使得π(vi)π(xvi)?{6,7,8,…,k},則我們可以交換邊xvi和邊xy所染的顏色而得到圖G′的一個(gè)新的k-無圈邊染色,此時(shí)問題即轉(zhuǎn)化為上一種情況.從而對(duì)任意頂點(diǎn)vi(i∈{1,2,3,4}),一定存在至少一種顏色α,使得α∈π(vi)π(xvi)且α∈{1,2,3,4,5}π(xvi).如果存在一個(gè)頂點(diǎn)(不妨設(shè)為v1)使得5?π(v1),則顏色集{2,3,4}中至少有一種顏色在頂點(diǎn)v1表現(xiàn).當(dāng)v1僅表現(xiàn)顏色集{2,3,4}中的一種顏色(不妨設(shè)為2)時(shí),此時(shí)存在一種顏色α∈{6,7,8,…,k}{π(v1)∪π(v2)},使得邊xv1染上顏色α,邊xv染上顏色1能夠成圖G的一個(gè)k-無圈邊染色.當(dāng)頂點(diǎn)v1表現(xiàn)了顏色集{2,3,4}中的兩種顏色(不妨設(shè)π(v1)={2,3})時(shí),此時(shí)亦存在一種顏色α∈{6,7,8,…,k}{π(v2)∪π(v3)},使得邊xv1染上顏色α,邊xv染上顏色1能夠成圖G的一個(gè)k-無圈邊染色.從而對(duì)任意頂點(diǎn)vi(i∈{1,2,3,4}),都有5∈π(vi).同時(shí)我們可以得到一定存在一種顏色α∈{6,7,8,…,k}使得對(duì)任意頂點(diǎn)vi(i∈{1,2,3,4}),α?π(vi).我們將邊xv1染上顏色α,xy染上顏色1可構(gòu)成圖G′的一個(gè)新的k-無圈邊染色,此時(shí)問題即轉(zhuǎn)化為前一種情況.

(C) 如果|π(x)∩π(v)|=2,如果π(x)∩π(v)={1,2}或{1,3}或{1,4}或{2,3}或{2,4}或{3,4}時(shí),我們有|π(x)∪π(v)∪π(WG′(x,v))|≤9

因?yàn)閐(y)≤Δ(G)-1,從而存在一種顏色α∈{6,7,…,k}使得α不在頂點(diǎn)y表現(xiàn),不妨設(shè)其為顏色6,如果6?π(v1),則我們可將邊xv染上顏色6而得到圖G的一個(gè)k-無圈邊染色,從而6∈π(v1).我們不妨設(shè)π(v1s1)=6,如果π(v1t1)?{2,3,4,5},則一定存在一種顏色α∈C{1,2,3,4,5,6,π(v1t1)},使得邊xv1染上顏色α后仍是圖G′的一個(gè)k-無圈邊染色,此時(shí)問題即轉(zhuǎn)化為情況6(B).從而π(v1t1)∈{2,3,4,5},當(dāng)π(v1t1)=2時(shí),我們可以找到一種顏色α,使得α∈C{1,2,3,4,5,6,π(v2s2),π(v2t2)}且當(dāng)邊xv1重新染上顏色α后仍是圖G′的一個(gè)k-無圈邊染色,此時(shí)問題即轉(zhuǎn)化為情況6(B).當(dāng)π(v1t1)=3或4時(shí),亦可由π(v1t1)=2時(shí)類似的證明將其問題轉(zhuǎn)化為情況6(B).當(dāng)π(v1t1)=5時(shí),如果存在一種顏色α∈{7,8,…,k}使得α不在頂點(diǎn)y表現(xiàn),則我們可將邊xv1重新染上顏色α而構(gòu)成圖G′的一個(gè)k-無圈邊染色,此時(shí)問題即轉(zhuǎn)化為情形6(2).否則π(y)={5,7,8,…,k}且d(y)=Δ(G)-1,此時(shí)我們將邊xy重新染上顏色6亦可得到圖G′的一個(gè)k-無圈邊染色,此時(shí)問題即轉(zhuǎn)化為情況6(B).

情況7設(shè)x是一個(gè)7度點(diǎn),鄰接7個(gè)度為3度的點(diǎn),設(shè)x的鄰點(diǎn)分別為vi,i=1,2,…,7,讓圖H=G-xv7,由圖G的最小性可知,C是圖H的一個(gè)無圈k.我們不防設(shè)邊C(xvi)=i,i=(1,2,…,6),若|C(x)∩C(v7)|=0則可以對(duì)邊xv7染顏色α∈l{C(x)∩C(v7)},既可以得到圖G的一個(gè)無圈k染色.若|C(x)∩C(v7)|=1,不使一般性可以假設(shè)C(v7)∈{1,7},因?yàn)閨C(x)∪C(v1)∪C(v7)|≤9,Δ≥7,則可以對(duì)邊xv7染顏色β∈l{C(x)∩C(v7)∩C(v1)},則可以得到圖G的一個(gè)無圈k染色.|C(x)∩C(v7)|=2,不使一般性可以假設(shè)C(v7)∈{1,2},因?yàn)閨C(x)∪C(v1)∪C(v2)|≤10,Δ≥7,則可以對(duì)邊xv7染顏色γ∈l{C(x)∩C(v2)∩C(v1)},則可以得到圖G的一個(gè)無圈k染色.

情況8設(shè)x是圖G的一個(gè)點(diǎn),且點(diǎn)x的度數(shù)大于等于7時(shí),x至少鄰接d(x)-3個(gè)2度點(diǎn),其中一個(gè)可以是3度點(diǎn).不妨設(shè)x的2度鄰點(diǎn)分別為y,yi(i=2,3,…,d(x)-3),v1是定點(diǎn)y的另外一個(gè)鄰點(diǎn),其中一個(gè)可以是3度點(diǎn).z1,z2,z3為剩下的3個(gè)點(diǎn).讓H=G-xy,由圖G的最小性可知,C是圖H的一個(gè)無圈k.可以設(shè)xyi染顏色{i},{i=2,3,…,d(x)-3},則邊xzi分別染顏色{i=d(x)-2,d(x)-1,d(x)}若|C(x)∩C(y)|=0,則可以對(duì)邊xy染顏色α∈l{C(x)∪C(y)},則可以得到圖G的一個(gè)無圈k染色.若果|C(x)∩C(y)|=1時(shí),若邊yv1∈{2,3,…,d(x)-3}設(shè)C(yv1)=2,則讓邊xy染顏色β∈l{C(x)∪C(y2)}我們即可得到圖G的一個(gè)無圈k染色.如果yv1∈{d(x)-2,d(x)-1,d(x)},因?yàn)閐(v1)≤Δ,而且k=Δ+4,則對(duì)邊yv1染顏色γ?{C(v1),d(x)-2,d(x)-1,d(x)},則可以得到圖H的一個(gè)無圈k染色C′,則根據(jù)前面的證明即可得到圖G的一個(gè)無圈k染色.

在上面的情況的證明中我們得到圖G的一個(gè)無圈k染色,與假設(shè)矛盾.所以我們即可以得到定理一是成立的.

由引理2,及性質(zhì)1,既可以證明定理2是成立的.

參考文獻(xiàn)：

[1]West D B.Tntroduction to Graph Theory[M]．Prentice Hall,Upper Saddle River,2001.

[2]Alon N,Sudakov,Zaks A. Acycle coloring of graphs[J]．J GraphTheory,2001,37:157-167.

[3]Alon N,McDiarmid C J H,Reed B A.Acycli coloring of graphs[J]．Random Structures Algorithms,1991,2:277-288.

[4]Basavaraju,Chandran L S. Acyclecoloring of subcubic graphs[J]．Discrete Math,2008,308: 6650-6653.

[5]Fiedorowicz A,Haluszczak M,Naraynan N. About acyclic edge colourings of planar graphs[J]．Tnform Process Lett,2008,108:412-417.

[6]Mieczyslaw,Borowiecki,Anna. Fiedorowicz,Acyclic dege colouring of planar graphsWithout short cycles[J]．Tn Faculty of Mathematic,Computer Science and Econometrics,University of Zielona Gora,Z,Szafrana 4a:65-516.

[7]Wei D,Xu B B.Some results on acyclic edge coloring of piane graphs[J]．Information Processing Letters,2010,110: 887-892.

[8]Montassier M,Ochem P,Raspaud A. On the acyclic choosability of graphs[J]．J.Graph Theory,2006,51:281-300.

[9]Molloy M,Reed B. Futher algorithmic aspects of the local lemma[J]．Tn Proceedings of the 30thAnnual ACM Symposium on Theoy of Computing,1998:524-529.

[10]Muthu R,Narayanan ,Subramanian C R. Optimal acycle edge colouring of grid like graphs[J]．TnComputing and Combinatorics,12th COCOON,Taipei,Taiwan,2006,4508:144-152.

[11]Muthu R,Narayanan,Subramanian C R. Acyclic edge colouring of outerplanar graphs[J]．TnAlgorithmic Aspects in Tnformation and Management 3th AAIM Portlang,USA,2007,4508:144-152.

[12]Skulrattanakulchai S. Acyclic coloring of subcubic graphs[J]．Tnform Process Lett,2004,92:161-167.