關于平面圖的7-全可染性的一個注記*

陶 鑫， 王應前

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

本文的圖指的是有限簡單無向圖，文中未加定義的術語和記號參閱文獻［1］．

設G=(V，E)表示頂點集為V、邊集為 E的圖．若能用k種顏色對G進行染色，使得任意2個相鄰或相關聯的元素染有不同的色，則稱G是k-全可染的．設F，Δ和δ分別表示平面圖G的面集、最大度和最小度．顯然，給每一個圖進行全染色至少要用Δ+1個色．

猜想1［1］任何簡單圖G都是(Δ+2)-全可染的．

這一猜想被稱為全染色猜想，簡記為TCC．即使對于平面圖，TCC在目前還沒有得到完整證明．剩下未解決的情形是Δ=6［2-8］．有趣的是，對于簡單平面圖，大多數情況是(Δ+1)-全可染的［9-10］．

猜想2［11］若G是4≤Δ≤8的簡單平面圖，則G是(Δ+1)-全可染的．

對此，文獻［12］證明了Δ≥7且不含有4-圈的平面圖是(Δ+1)-全可染的;文獻［11］證明了Δ=7且不含相鄰三角形的平面圖是8-全可染的．筆者則研究了Δ=6且不含5-圈和6-圈的平面圖的全染色問題．

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

證明 假設定理1不成立，并設G是定理1的一個使σ(G)=|V|+|E|最小的反例，即G本身不是7-全可染的，但它的每一個真子圖都是7-全可染的，則可得斷言1．

斷言1［9］G是2-連通的，從而δ≥2且G的每個面的邊界都是圈．

把度為k的點叫做k-點．類似地，度不小于k的點叫做k+-點，度不大于k的點叫做k－-點．

斷言2［12］設 xy∈E．若 d(x)≤3，則 d(x)+d(y)≥Δ +2=8．特別地，G 中2-點只與6-點相鄰，3-點只與5+-點相鄰．

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

圖1 G不含有的構形

只證第5種情形(如圖1(e)所示)，其他情形的證明可參閱文獻［10-11，13］．假設G含有如圖1(e)所示的構形．根據 σ(G)的極小性知，G'=G －uv是7-全可染的．令 φ:V(G')∪E(G')→{1，2，…，7}是G'的一個7-全染色．設對于x∈V，S(x)是與頂點x以及與x相關聯的邊染得的顏色集．如圖1(e)所示，設 S(u)={1，2，…，6}，其中 φ(uq)=3，φ(uw)=4，φ(vm)=7，因此 φ(pq)=7．否則將 3 染給 uv，7 染給uq，這樣得到G的一個7-全染色，矛盾．此時交換pq與pw的顏色，將3染給uv，7染給uq，這樣得到了G的一個7-全染色，矛盾．因此，斷言3成立．

以下將運用Discharging方法導出完成定理1證明所需要的矛盾．

首先，給G的頂點v分配初始權ch(v)=2d(v)－6，給G的面f分配初始權ch(f)=d(f)－6．由握

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

權轉移規則如下(如圖2所示):

R1:轉向2-點的權

與2-點相鄰的2個6-點都向此2-點轉移權1．

R2:轉向3-面的權

由斷言2知，3-面上只有1個3－-點，因此

R2．1:若3-面含有3－-點，則此3-面上的2 個5+-點都向此

R2．2:若3-面不含3－-點，則此3-面上的3 個4+-點都向此3-面轉移權 1．

R3:轉向4-面的權

R3．1:若4-面含有2個3－-點，則此4-面上的2個5+-點都向此4-面轉移權1;

R3．2:若4-面含有1個3－-點，則此4-面上與此3－-點相對的那個4+-點向此

R3．3:若4-面不含3－-點，則此4-面上的4 個4+-點都向此4-面

圖2 權轉移規則

首先考察面的新權．

設 f為3-面．若 f有1 個3－-點，則根據R2．2，ch'(f)=ch(f)+1 ×3=0．

設 f為4-面．若 f含有2 個3－-點，則根據 R3．1，ch'(f)=ch(f)+1 ×2=0;若f含1 個3－-點，則根據

由G不含5-圈和6-圈知G不含5-面和6-面，故無需驗證5-面和6-面的新權．

設f為7+-面．由權轉移規則知f既不轉出權也不接受權，因此ch'(f)=ch(f)=d(f)－6＞0．

綜上所述，對任意的面f∈F，ch'(f)≥0．

其次考察頂點的新權．

設v為2-點．由斷言2和R1知，ch'(v)=ch(v)+1×2= －2+2=0．

設v為3-點．由權轉移規則知v既不轉出權也不接受權，故ch'(v)=ch(v)=0．

下面用t表示與v關聯的3-面個數．

設 v為4-點．由 G 不含5-圈和6-圈知 t≤2，且 v至少與2 個7+-面關聯．根據 R2．2 和 R2．3，v至多轉移權1給每個相關聯的3-面，至多轉移

設v為5-點．由G不含5-圈和6-圈知t≤3，且v至少與2個7+-面關聯．又由斷言3(如圖1(a)所示)知v至多與2個含有3－-點的3-面關聯，根據R2和R3

設v為6-點．用n表示與v相鄰的2-點個數，顯然，n≤6．與6-點相鄰的2-點分布情況如圖3所示．下面根據n的大小來討論v的新權:

圖3 與6-點相鄰的2-點分布情況(2≤n≤4)

n=6．由斷言3(如圖1(d)所示)知，v不與3-面關聯．由G不含5-圈和6-圈以及斷言3(如圖1(e)所示)知，與v關聯且關聯2個與v相鄰的2-點的面是7+-面．因此，v關聯6個7+-面，根據R1，

n=5．由斷言3(如圖1(d)所示)知t=0．由G不含5-圈和6-圈知，v至少關聯5個7+-面，根據R1和R3，

n=4．如圖3(a1)、圖 3(a2)、圖 3(a3)所示，由斷言3(如圖1(d)所示)知 t≤1．若 t=1，則由 G 不則v至少關聯 4個7+-面，根據R1和R3，ch'(v)≥ch(v)－1×4－1×2－0×4=0．

n=3．如圖3(b1)、圖3(b2)、圖3(b3)所示，由斷言3(如圖1(d)所示)知 t≤2．若1≤t≤2，則由 G不含5-圈和6-圈知v至少關聯4個7+-面，根據R1，R2和R3，

若 t=0，則 v至少關聯3個7+-面，根據 R1和 R3，ch'(v)≥ch(v)－1×3－0×3－1×3=0．

n=2．如圖3(c1)、圖3(c2)、圖3(c3)所示，由斷言 3(如圖1(d)所示)知 t≤2．若1≤t≤2，則由 G不含5-圈和6-圈知v至少關聯3個7+-面，根據R1，R2．1和R3，

若t=0，則v至少關聯2個7+-面，根據R1和R3，ch'(v)≥ch(v)－1×2－0×2－1×4=0．

設含有2-點的3-面是特殊3-面，記作s-面．由斷言3(如圖1(b)和圖1(c)所示)知，若6-點與一個s-面關聯，則6-點不與其他含有3－-點的3-面關聯．

n=1．若v與s-面關聯，則由 G不含5-圈和6-圈知 t≤4，且 v至少關聯2個7+-面，根據 R1，R2和

若v不與s-面關聯，則 t≤3．若t=3，則根據G不含5-圈和6-圈，v要關聯3個7+-面，從而

若0≤t≤2，則v至少關聯2個7+-面，從而

n=0．由G不含5-圈和6-圈知t≤4，且v至少關聯2個7+-面，根據R1，R2和R3，

至此，對任意的x∈V∪F，ch'(x)≥0已得到驗證．定理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］陳明，王應前．關于平面圖全染色的一個注記［J］．浙江師范大學學報:自然科學版，2007，30(4):421-423．

［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］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(1):2778-2784．

［12］Hou Jianfeng，Liu Guizhen，Cai Jiansheng．List edge and list total coloring of planar graphs without 4-cycles［J］．Theoret Comput Sci，2006，369(4):250-255．

［13］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．