關于最大度為7的平面圖全染色的一個注記＊

王應前， 孫 強， 陶 鑫

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

0 引言

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

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

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

1 結構

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

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

稱度為k的點為k-點．類似地，稱度不小于k的點為k+-點，度不大于k的點為k--點．

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

引理1和引理2的證明可參見文獻［9］．

引理3 G不含圖1所示的結構，其中標記為·的點在G中沒有其他鄰點．

圖1 G中不存在的結構

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

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

引理4 G不含圖2所示的結構，其中標記為·的點在G中沒有其他鄰點．

圖2 G中不存在的結構

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

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

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

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

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

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

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

2 權轉移

以下將運用Discharging方法導出完成定理1證明所需要的矛盾．首先，給G的頂點v分配初始權-12．

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

R1:給2-點v的權．

由引理3知，v只與7-點相鄰．每個與v相鄰的7-點轉權1給v．

R2:給3-面 f的權．

由引理2和引理3知，3-面上至多只有1個4--點．

圖3 權轉移規則

注1 6+-點不轉權給與其相關聯的6+-面;6+-點至多轉與其相關聯的4-面;進一步，5-點至多轉

由以上權轉移規則可知，對G中的每個面f均有ch'(f)≥0成立，且對所有的2-點v，ch'(v)≥0也成立．下面只需驗證G中3+-點的新權．

設v為3-點．由上面的權轉移規則可知，3-點既沒轉出權也不接收權，故ch'(v)=ch(v)=0．下面用t表示與v相關聯的3-面個數．

設v為7-點．設n為與7-點v相鄰的2-點個數，則n≤7．

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

注2 設面f與v相關聯，且v至少與1個不在f上的2-點相鄰．若f與2個2-點相關聯，同時這2個2-點與v相鄰，則由引理3知f是一個6+-面;若f只與1個2-點相關聯，同時這個2-點與v相鄰，則由引理3知f是一個4+-面．

當2≤n≤5時，n個2-點在7-點v周圍的分布情況如圖4所示．

圖4 當2≤n≤5時，n個2-點在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．