關(guān)于平面圖的7-全可染性的一個(gè)注記*

陶 鑫， 王應(yīng)前

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

本文的圖指的是有限簡(jiǎn)單無(wú)向圖，文中未加定義的術(shù)語(yǔ)和記號(hào)參閱文獻(xiàn)［1］．

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

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

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

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

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

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

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

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

把度為k的點(diǎn)叫做k-點(diǎn)．類(lèi)似地，度不小于k的點(diǎn)叫做k+-點(diǎn)，度不大于k的點(diǎn)叫做k－-點(diǎn)．

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

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

圖1 G不含有的構(gòu)形

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

以下將運(yùn)用Discharging方法導(dǎo)出完成定理1證明所需要的矛盾．

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

下面將定義一個(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ī)則如下(如圖2所示):

R1:轉(zhuǎn)向2-點(diǎn)的權(quán)

與2-點(diǎn)相鄰的2個(gè)6-點(diǎn)都向此2-點(diǎn)轉(zhuǎn)移權(quán)1．

R2:轉(zhuǎn)向3-面的權(quán)

由斷言2知，3-面上只有1個(gè)3－-點(diǎn)，因此

R2．1:若3-面含有3－-點(diǎn)，則此3-面上的2 個(gè)5+-點(diǎn)都向此

R2．2:若3-面不含3－-點(diǎn)，則此3-面上的3 個(gè)4+-點(diǎn)都向此3-面轉(zhuǎn)移權(quán) 1．

R3:轉(zhuǎn)向4-面的權(quán)

R3．1:若4-面含有2個(gè)3－-點(diǎn)，則此4-面上的2個(gè)5+-點(diǎn)都向此4-面轉(zhuǎn)移權(quán)1;

R3．2:若4-面含有1個(gè)3－-點(diǎn)，則此4-面上與此3－-點(diǎn)相對(duì)的那個(gè)4+-點(diǎn)向此

R3．3:若4-面不含3－-點(diǎn)，則此4-面上的4 個(gè)4+-點(diǎn)都向此4-面

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

首先考察面的新權(quán)．

設(shè) f為3-面．若 f有1 個(gè)3－-點(diǎn)，則根據(jù)R2．2，ch'(f)=ch(f)+1 ×3=0．

設(shè) f為4-面．若 f含有2 個(gè)3－-點(diǎn)，則根據(jù) R3．1，ch'(f)=ch(f)+1 ×2=0;若f含1 個(gè)3－-點(diǎn)，則根據(jù)

由G不含5-圈和6-圈知G不含5-面和6-面，故無(wú)需驗(yàn)證5-面和6-面的新權(quán)．

設(shè)f為7+-面．由權(quán)轉(zhuǎn)移規(guī)則知f既不轉(zhuǎn)出權(quán)也不接受權(quán)，因此ch'(f)=ch(f)=d(f)－6＞0．

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

其次考察頂點(diǎn)的新權(quán)．

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

設(shè)v為3-點(diǎn)．由權(quán)轉(zhuǎn)移規(guī)則知v既不轉(zhuǎn)出權(quán)也不接受權(quán)，故ch'(v)=ch(v)=0．

下面用t表示與v關(guān)聯(lián)的3-面?zhèn)€數(shù)．

設(shè) v為4-點(diǎn)．由 G 不含5-圈和6-圈知 t≤2，且 v至少與2 個(gè)7+-面關(guān)聯(lián)．根據(jù) R2．2 和 R2．3，v至多轉(zhuǎn)移權(quán)1給每個(gè)相關(guān)聯(lián)的3-面，至多轉(zhuǎn)移

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

設(shè)v為6-點(diǎn)．用n表示與v相鄰的2-點(diǎn)個(gè)數(shù)，顯然，n≤6．與6-點(diǎn)相鄰的2-點(diǎn)分布情況如圖3所示．下面根據(jù)n的大小來(lái)討論v的新權(quán):

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

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

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

n=4．如圖3(a1)、圖 3(a2)、圖 3(a3)所示，由斷言3(如圖1(d)所示)知 t≤1．若 t=1，則由 G 不則v至少關(guān)聯(lián) 4個(gè)7+-面，根據(jù)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至少關(guān)聯(lián)4個(gè)7+-面，根據(jù)R1，R2和R3，

若 t=0，則 v至少關(guān)聯(lián)3個(gè)7+-面，根據(jù) 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至少關(guān)聯(lián)3個(gè)7+-面，根據(jù)R1，R2．1和R3，

若t=0，則v至少關(guān)聯(lián)2個(gè)7+-面，根據(jù)R1和R3，ch'(v)≥ch(v)－1×2－0×2－1×4=0．

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

n=1．若v與s-面關(guān)聯(lián)，則由 G不含5-圈和6-圈知 t≤4，且 v至少關(guān)聯(lián)2個(gè)7+-面，根據(jù) R1，R2和

若v不與s-面關(guān)聯(lián)，則 t≤3．若t=3，則根據(jù)G不含5-圈和6-圈，v要關(guān)聯(lián)3個(gè)7+-面，從而

若0≤t≤2，則v至少關(guān)聯(lián)2個(gè)7+-面，從而

n=0．由G不含5-圈和6-圈知t≤4，且v至少關(guān)聯(lián)2個(gè)7+-面，根據(jù)R1，R2和R3，

至此，對(duì)任意的x∈V∪F，ch'(x)≥0已得到驗(yàn)證．定理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］陳明，王應(yīng)前．關(guān)于平面圖全染色的一個(gè)注記［J］．浙江師范大學(xué)學(xué)報(bào):自然科學(xué)版，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．