王應(yīng)前， 孫 強(qiáng)， 陶 鑫

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

0 引言

本文未加定義的術(shù)語和記號(hào)請(qǐng)參閱文獻(xiàn)［1］．除特別說明外，本文所研究的圖都是有限簡(jiǎn)單無向圖．用V，E，F(xiàn)，Δ和δ分別表示平面圖G的頂點(diǎn)集、邊集、面集、最大度和最小度．若V∪E中的元素能用k個(gè)顏色進(jìn)行染色，使得任意2個(gè)相鄰或相關(guān)聯(lián)的元素染有不同的色，則稱G是k-全可染的．顯然，給每個(gè)圖進(jìn)行全染色至少要用Δ+1個(gè)色．Vizing猜想:任何簡(jiǎn)單圖G都是(Δ+2)-全可染的．這一猜想被稱為全染色猜想，簡(jiǎn)記為TCC．

雖然已有大量的文獻(xiàn)［2-8］對(duì)TCC進(jìn)行了深入的研究，但是即使對(duì)于平面圖，TCC也仍未得到完整的證明，唯一未解決的困難情形是Δ=6．對(duì)于簡(jiǎn)單平面圖，大多數(shù)情況下是(Δ+1)-全可染的．文獻(xiàn)［9-11］相繼證明了Δ≥11，Δ=10，Δ=9的平面圖是(Δ+1)-全可染的．對(duì)于Δ≤8的平面圖，要得到如文獻(xiàn)［9-11］那樣簡(jiǎn)潔的結(jié)果似乎非常困難．本文研究了Δ=7的平面圖的全可染性，得到如下結(jié)果:

定理1 若G是Δ=7且不含帶弦4-圈和帶弦5-圈的平面圖，則G是8-全可染的．

1 結(jié)構(gòu)

假設(shè)定理1不成立，設(shè)G是定理1的一個(gè)使σ(G)=|V|+|E|最小的反例，即G本身不是8-全可染的，但它的每個(gè)真子圖都是8-全可染的，則G有以下幾個(gè)性質(zhì):

引理1 G是2-連通的，從而δ≥2且G的每個(gè)面的邊界都是圈．

稱度為k的點(diǎn)為k-點(diǎn)．類似地，稱度不小于k的點(diǎn)為k+-點(diǎn)，度不大于k的點(diǎn)為k--點(diǎn)．

引理2 設(shè)xy∈E．若d(x)≤3，則d(x)+d(y)≥Δ+2=9．特別地，G中2-點(diǎn)只與7-點(diǎn)相鄰，3-點(diǎn)只與6+-點(diǎn)相鄰．

引理1和引理2的證明可參見文獻(xiàn)［9］．

引理3 G不含圖1所示的結(jié)構(gòu)，其中標(biāo)記為·的點(diǎn)在G中沒有其他鄰點(diǎn)．

圖1 G中不存在的結(jié)構(gòu)

設(shè)f∈F，f的周界(即按某個(gè)方向繞f一周的閉途徑)的長(zhǎng)度記為d(f)，稱其為面f的度．稱d(f)=k的面為k-面．類似地可定義k+-面和k--面．若一個(gè)k-面沿著某個(gè)方向的點(diǎn)依次為v1，v2，…，vk，則稱這個(gè)面為一個(gè)(d(v1)，d(v2)，…，d(vk))-面．

下面將給出引理3(d)的證明，其余證明可參閱文獻(xiàn)［12-13］．

引理4 G不含圖2所示的結(jié)構(gòu)，其中標(biāo)記為·的點(diǎn)在G中沒有其他鄰點(diǎn)．

圖2 G中不存在的結(jié)構(gòu)

情形 1 |{φ(e8)，φ(e9)，φ(e10)，φ(e11)}|≥2．由于 E，F(xiàn)，H 都是 5-點(diǎn)，此時(shí)先依次染好 e1，e3，e6，染的顏色分別記為 α，β，γ;再將{c(E)，c(H)，c(F)}{α，β，γ}中的色染給{e2，e4，e5，e7}中的若干條邊;然后再染好{e2，e4，e5，e7}中剩下的邊，此時(shí)O的禁用色恰好為7個(gè)，故頂點(diǎn)O可染;最后再染好M，N，L，P，從而得到G的一個(gè)8-全染色，矛盾．

情形2 |{φ(e8)，φ(e9)，φ(e10)，φ(e11)}|=1．設(shè) φ(e8)=φ(e9)=φ(e10)=φ(e11)=ζ，若 ζ?{φ(E)，φ(F)，φ(H)}，此時(shí)先依次染好 e1，e3，e6;再按照情形1的染色方案得到 G的一個(gè)8-全染色，矛盾．故設(shè) ζ∈{φ(E)，φ(F)，φ(H)}，令 ζ=φ(E)．當(dāng)|S［E］|≤7 時(shí)，改染頂點(diǎn) E 的顏色為 θ，讓 e1染φ(E)，再依次染好e3，e6，此時(shí)可按照情形1的染色方案易得G的一個(gè)8-全染色，矛盾;當(dāng)|S［E］|=8時(shí)，EA和EB中至多只有1條邊(不妨設(shè)為EA)與E的鄰點(diǎn)染有相同的顏色，交換EB與e8的顏色，將頂點(diǎn)E的顏色改染為φ(EB)，此時(shí)先依次染好e1，e3，e6，然后按照情形1的染色方案易得G的一個(gè)8-全染色，矛盾．同理可證當(dāng)ζ=φ(F)或φ(H)時(shí)，易得G的一個(gè)8-全染色，矛盾．說明G中不含如圖2(a)所示的結(jié)構(gòu)．

2)假設(shè)G中存在如圖2(b)所示的結(jié)構(gòu)，由σ(G)的極小性知，G'=G-O是8-全可染的．令φ:V(G')∪E(G')→{1，2，…，8}是 G'的一個(gè)8-全染色．抹去 M，N，L，C 的顏色．

情形 1 |{φ(e8)，φ(e9)，φ(e10)}|≥2．由于 A，B，D 都是 5-點(diǎn)，此時(shí)先依次染好 e7，e2，e4，e5，染的顏色分別記為 α，β，γ，η;再將{c(A)，c(B)，c(D)}{α，β，γ，η}中的色染給{e1，e3，e6}中的若干條邊;然后再染好{e1，e3，e6}中剩下的邊，此時(shí)O的禁用色恰好為7個(gè)，故O可染;最后再染好M，N，L，C，從而得到G的一個(gè)8-全染色，矛盾．

情形2 |{φ(e8)，φ(e9)，φ(e10)}|=1．設(shè) φ(e8)=φ(e9)=φ(e10)=φ(e11)=ζ．若 ζ?{φ(A)，φ(B)，φ(D)}，此時(shí)先依次染好e7，e2，e4，e5;再按照情形1的染色方案得到G 的一個(gè)8-全染色，矛盾．故設(shè) ζ∈{φ(A)，φ(B)，φ(D)}，令 ζ=φ(A)．當(dāng) |S［A］|≤7 時(shí)，改染頂點(diǎn) A 的顏色為 θ，讓 e2染 φ(A)，再依次染好e7，e4，e5，此時(shí)可按照情形1的染色方案易得G的一個(gè)8-全染色，矛盾;當(dāng)|S［A］|=8時(shí)，EA和HA中至多只有1條邊(不妨設(shè)為EA)與A的鄰點(diǎn)染有相同的顏色，交換HA與e10的顏色，將頂點(diǎn)A的顏色改染為φ(HA)，同樣可按照情形1的染色方案易得G的一個(gè)8-全染色，矛盾．同理可證，若ζ=φ(B)，則易得G的一個(gè)8-全染色，矛盾．

若ζ=φ(D)且 φ(CI)=φ(D)，則當(dāng) |S［D］|≤7時(shí)，改染頂點(diǎn)D的顏色為 θ，讓e4染 φ(D)，按照情形1的染色方案易得G的一個(gè)8-全染色，矛盾;當(dāng)|S［D］|=8時(shí)，DH和DI中至多只有1條邊與D的鄰點(diǎn)染有相同的顏色，若DI與D的鄰點(diǎn)染有相同的顏色，則交換DH與e10的顏色，并將頂點(diǎn)D的顏色改染為φ(DH)，此時(shí)可按照情形1的染色方案易得G的一個(gè)8-全染色，矛盾，若DH與D的鄰點(diǎn)染有相同的顏色，則交換CI和DI的顏色，接著交換CF和e9的顏色，將頂點(diǎn)D的顏色改染為φ(DI)，可按照情形1的染色方案易得G的一個(gè)8全染色，矛盾．

若ζ=φ(D)且φ(CI)≠φ(D)，則交換CF和e9的顏色，此時(shí)可按照情形1的染色方案易得G的一個(gè)8-全染色，矛盾．說明G中不含圖2(b)所示的結(jié)構(gòu)．引理4證畢．

2 權(quán)轉(zhuǎn)移

以下將運(yùn)用Discharging方法導(dǎo)出完成定理1證明所需要的矛盾．首先，給G的頂點(diǎn)v分配初始權(quán)-12．

以下將定義一個(gè)權(quán)轉(zhuǎn)移規(guī)則，重新分配點(diǎn)和面的權(quán)．設(shè)ch'(x)是重新分配點(diǎn)和面的權(quán)后元素x∈同一個(gè)圖的點(diǎn)和面之間進(jìn)行權(quán)轉(zhuǎn)移，權(quán)的總和應(yīng)該保持不變，便得出-12≥0，即得到了證明定理1所需要的矛盾．權(quán)轉(zhuǎn)移規(guī)則如圖3所示．

R1:給2-點(diǎn)v的權(quán)．

由引理3知，v只與7-點(diǎn)相鄰．每個(gè)與v相鄰的7-點(diǎn)轉(zhuǎn)權(quán)1給v．

R2:給3-面 f的權(quán)．

由引理2和引理3知，3-面上至多只有1個(gè)4--點(diǎn)．

圖3 權(quán)轉(zhuǎn)移規(guī)則

注1 6+-點(diǎn)不轉(zhuǎn)權(quán)給與其相關(guān)聯(lián)的6+-面;6+-點(diǎn)至多轉(zhuǎn)與其相關(guān)聯(lián)的4-面;進(jìn)一步，5-點(diǎn)至多轉(zhuǎn)

由以上權(quán)轉(zhuǎn)移規(guī)則可知，對(duì)G中的每個(gè)面f均有ch'(f)≥0成立，且對(duì)所有的2-點(diǎn)v，ch'(v)≥0也成立．下面只需驗(yàn)證G中3+-點(diǎn)的新權(quán)．

設(shè)v為3-點(diǎn)．由上面的權(quán)轉(zhuǎn)移規(guī)則可知，3-點(diǎn)既沒轉(zhuǎn)出權(quán)也不接收權(quán)，故ch'(v)=ch(v)=0．下面用t表示與v相關(guān)聯(lián)的3-面?zhèn)€數(shù)．

設(shè)v為7-點(diǎn)．設(shè)n為與7-點(diǎn)v相鄰的2-點(diǎn)個(gè)數(shù)，則n≤7．

為方便起見，先引入幾個(gè)記號(hào):τ(v→)表示從v轉(zhuǎn)出的權(quán)和;t表示與v相關(guān)聯(lián)的3-面的個(gè)數(shù)．一些依次圍繞頂點(diǎn)v的面形成一個(gè)v扇，簡(jiǎn)稱為扇．稱一個(gè)扇是極大的，如果扇的始邊和終邊都是(7，2)邊(即連接7-點(diǎn)和2-點(diǎn)的邊)，而扇中與v相關(guān)聯(lián)的其他邊均不是(7，2)邊．通常把一個(gè)由k個(gè)面組成的扇

注2 設(shè)面f與v相關(guān)聯(lián)，且v至少與1個(gè)不在f上的2-點(diǎn)相鄰．若f與2個(gè)2-點(diǎn)相關(guān)聯(lián)，同時(shí)這2個(gè)2-點(diǎn)與v相鄰，則由引理3知f是一個(gè)6+-面;若f只與1個(gè)2-點(diǎn)相關(guān)聯(lián)，同時(shí)這個(gè)2-點(diǎn)與v相鄰，則由引理3知f是一個(gè)4+-面．

當(dāng)2≤n≤5時(shí)，n個(gè)2-點(diǎn)在7-點(diǎn)v周圍的分布情況如圖4所示．

圖4 當(dāng)2≤n≤5時(shí)，n個(gè)2-點(diǎn)在v周圍的分布情況

綜上即能證得定理1．

［1］Bondy J A，Murty U S R．Graph Theory［M］．Berlin:Springer，2008．

［2］Rosenfeld M．On the total coloring of certain graphs［J］．Israel J Math，1971，9(3):396-402．

［3］Kostochka A V．The total coloring of a multigraph with maximal degree 4［J］．Discrete Math，1977，17(2):161-163．

［4］Kostochka A V．The total chromatic number of any multigraph with maximal degree five is at most seven［J］．Discrete Math，1996，162(2):199-214．

［5］Borodin O V．On the total coloring of planar graphs［J］．J Reine Angew Math，1989，394(2):180-185．

［6］Yap H P．Total coloring of graphs［M］．Belin:Spring-Verlag，1996．

［7］Sanders D P，Zhao Yue．On total 9-coloring planar graphs of maximum degree seven［J］．J Graph Theory，1999，319(1):67-73．

［8］Wang Yingqian，Shangguan Minle，Li Qiao．On total chromatic number of planar graphs without 4-cycles［J］．Sci China Ser A，2007，50(1):81-86．

［9］Borodin O V，Kostochka A V，Woodall D R．Total coloring of planar graphs with large maximum degree［J］．J Graph Theory，1997，26(1):53-59．

［10］Wang Weifan．Total chromatic number of planar graphs with maximum degree ten［J］．J Graph Theory，2007，54(1):91-102．

［11］Kowalik L，Sereni J S，Skrekovski R．Total coloring of plane graphs with maximum degree nine［J］．SIAM J Discrete Math，2008，22(4):1462-1479．

［12］Du Dingzhu，Shen Lan，Wang Yingqian．Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable［J］．Discrete Appl Math，2009，157(13):2778-2784．

［13］Shen Lan，Wang Yingqian，Wang Weifan，et al．On the 9 total colorability of planar graphs with maximum degree 8 andwithout intersecting triangles［J］．Applied Mathematics Letters，2009，22(9):1369-1373．