卜月華， 鮑旭東

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

沒(méi)有7－圈的平面圖的BB－染色*

卜月華， 鮑旭東

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

研究了沒(méi)有7－圈的連通平面圖的BB－染色問(wèn)題.應(yīng)用經(jīng)典的Discharging方法，證明了沒(méi)有7－圈且不含相鄰4－圈的連通平面圖G，存在G的一棵生成樹(shù)T，使得(G，T)是BB－4－可染的.這一結(jié)果進(jìn)一步拓展了平面圖的BB－4－可染的充分條件.

平面圖;BB－染色;生成樹(shù);圈

0 引言

本文只考慮有限無(wú)向簡(jiǎn)單圖.對(duì)于平面圖G，用V(G)，E(G)，F(xiàn)(G)，Δ(G)和δ(G)表示圖G的頂點(diǎn)集、邊集、面集、最大度和最小度.稱(chēng)平面圖G的度數(shù)為k(至多為k，至少為k)的頂點(diǎn)為k－點(diǎn)(k－－點(diǎn)，k+－點(diǎn)).對(duì)于平面圖，可類(lèi)似地定義k－面、k－－面、k+－面.若2個(gè)面或者2個(gè)圈至少有一條公共邊，則稱(chēng)這2個(gè)面或者2個(gè)圈相鄰;若2個(gè)面或者2個(gè)圈有一個(gè)公共點(diǎn)，則稱(chēng)這2個(gè)面或者2個(gè)圈相交.特別地，稱(chēng)3－圈為三角形.對(duì)于平面圖G，若δ(G)≥2，則k(k≤5)－面均為簡(jiǎn)單面.本文未定義的符號(hào)和說(shuō)明參見(jiàn)文獻(xiàn)［1］.

設(shè)G=(V，E)是一個(gè)簡(jiǎn)單圖，C是一個(gè)顏色集合，則稱(chēng)從V到C的一個(gè)映射φ:V→C為G的一個(gè)頂點(diǎn)染色.又若相鄰的頂點(diǎn)染有不同的顏色，即uv∈E，使得φ(u)≠φ(v)，則稱(chēng)φ為G的一個(gè)正常染色，簡(jiǎn)稱(chēng)染色.進(jìn)一步，若|C|=k，則稱(chēng)φ為G的一個(gè)k－染色.若G有一個(gè)k－染色，則稱(chēng)G是k－可染的.稱(chēng)χ(G)=min{k|G是k－可染的}為G的色數(shù).

近幾年來(lái)，基于正常染色，許多學(xué)者提出了各式各樣的染色模型，其中BB－染色就是基于頻率分配問(wèn)題，是由Akiyama等［2］提出來(lái)的.設(shè)H為G的一個(gè)生成子圖，(G，H)的一個(gè)BB－k－染色是指一個(gè)映射φ:V(G)→{1，2，…，k}，滿(mǎn)足:1)若uv∈E(H)，則|φ(u)－φ(v)|≥2;2)若uv∈ E(G)E(H)，則|φ(u)－φ(v)|≥1.(G，H)的BB－色數(shù)是指最小的整數(shù)k，使得(G，H)是BB－k－可染的，記為χb(G，H).

Broersma等［3］研究了圖的色數(shù)與BB－色數(shù)之間的關(guān)系，證明了圖的BB－色數(shù)至多為2χ(G)－1，并且這個(gè)上界是可以達(dá)到的.近幾年來(lái)，關(guān)于BB－染色取得了一些突出的成果［4－5］.文獻(xiàn)［6］提出了如下問(wèn)題:對(duì)于任意含奇圈的連通平面圖G，若G的圍長(zhǎng)g≥k，則存在G的一棵生成樹(shù)T，使得χb(G，T)=4.設(shè)β為上述命題為真的最小正整數(shù)k，試確定β的值.文獻(xiàn)［6］指出，4≤β≤10;文獻(xiàn)［7－8］證明了:若連通平面圖G沒(méi)有5－圈或者沒(méi)有4－圈，則存在G的一棵生成樹(shù)T，使得χb(G，T)≤4;文獻(xiàn)［9］證明了:若連通平面圖G沒(méi)有6－圈或者沒(méi)有7－圈且不含相鄰三角形，則存在G的一棵生成樹(shù)T，使得χb(G，T)≤4.對(duì)于BB－染色，以下問(wèn)題值得進(jìn)一步探討:

問(wèn)題1 對(duì)于任意含有奇圈的連通平面圖G，是否存在G的一棵生成樹(shù)T，使得χb(G，T)=4?

問(wèn)題2 對(duì)于連通平面圖G，T為G的任意一棵生成樹(shù)，由四色定理可知，χb(G，T)≤7，那么能否證明χb(G，T)≤6?

問(wèn)題3 對(duì)于連通平面圖G，T為G的任意一棵生成樹(shù)，不利用四色定理，如何證明χb(G，T)≤7?本文主要證明了下面定理:

定理1 設(shè)G是一個(gè)沒(méi)有7－圈且不含相鄰4－圈的連通平面圖，則存在G的一棵生成樹(shù)T，使得χb(G，T)≤4.

1 定理1的證明

下面用反證法來(lái)證明定理1.假設(shè)平面圖G=(V，E，F(xiàn))是使σ(G)=|V|+|E|最小的一個(gè)反例，即G滿(mǎn)足:1)G是一個(gè)沒(méi)有7－圈且不含相鄰4－圈的連通平面圖，對(duì)于 G的任意一棵生成樹(shù) T，都有χb(G，T)≥5;2)對(duì)于頂點(diǎn)數(shù)與邊數(shù)之和小于σ(G)的連通平面圖G'，若G'沒(méi)有7－圈且不含相鄰4－圈，則存在G'的一棵生成樹(shù)T'，有χb(G'，T')≤4.

下面根據(jù)G的極小性，給出G的幾個(gè)結(jié)構(gòu)性質(zhì)和定義.

定義1 若一個(gè)4－點(diǎn)v關(guān)聯(lián)2個(gè)3－面和1個(gè)4－面，且這2個(gè)3－面不相鄰，則稱(chēng)此4－點(diǎn)為壞4－點(diǎn)，此4－面為壞4－面(如圖1所示的f1)，與壞4－面不相鄰且相交于頂點(diǎn)v的面稱(chēng)為好面(如圖1所示的f2).

圖1 壞4－點(diǎn)v，壞4－面f1，好面f2

圖G具有以下結(jié)構(gòu)性質(zhì):

性質(zhì)1［8］圖G不含1－點(diǎn).

性質(zhì)2［8］圖G不含2－點(diǎn).

性質(zhì)3［8］圖G不含3－點(diǎn).

下面運(yùn)用權(quán)轉(zhuǎn)移方法完成定理1的證明.

先假設(shè)平面圖G=(V，E，F(xiàn))是2－連通的，則G的每個(gè)面的邊界都是一個(gè)圈，G中每個(gè)頂點(diǎn)v關(guān)聯(lián)d(v)個(gè)面.根據(jù)連通平面圖的Euler公式|V|+|F|－|E|=2及度和公式，有

對(duì)于任意的x∈V(G)∪F(G)，構(gòu)造一個(gè)權(quán)函數(shù)w(x)，其中當(dāng)v∈V(G)時(shí)，w(v)=2d(v)－6，當(dāng)f∈F(G)時(shí)，w(f)=d(f)－6，則

下面根據(jù)G的結(jié)構(gòu)性質(zhì)，在保持總的權(quán)和不變的情況下，對(duì)G中的點(diǎn)和面按照一定的權(quán)轉(zhuǎn)移規(guī)則進(jìn)行轉(zhuǎn)權(quán)，經(jīng)過(guò)權(quán)轉(zhuǎn)移后得到一個(gè)新的權(quán)函數(shù)w'(x).將證明對(duì)于任意的x∈V(G)∪F(G)，都有w'(x)≥0，從而得到如下矛盾:

該矛盾說(shuō)明反例G不存在，從而完成定理1的證明.

下面給出如下權(quán)轉(zhuǎn)移規(guī)則:

R0:d(v)=4.

R0.1:若v不關(guān)聯(lián)3－面，則v給關(guān)聯(lián)的4+－面轉(zhuǎn)權(quán)

R0.2:若v關(guān)聯(lián)一個(gè)3－面，則v給關(guān)聯(lián)的3－面轉(zhuǎn)權(quán)1，給關(guān)聯(lián)的4－面轉(zhuǎn)權(quán)，給關(guān)聯(lián)的5－面轉(zhuǎn)權(quán)

R0.3:若v關(guān)聯(lián)2個(gè)3－面，則v給關(guān)聯(lián)的3－面轉(zhuǎn)權(quán)1.

R1:d(v)=5.

R1.1:若v不關(guān)聯(lián)3－面，則v給關(guān)聯(lián)的4+－面轉(zhuǎn)權(quán)

R1.2:若v關(guān)聯(lián)1個(gè)3－面，則v給關(guān)聯(lián)的3－面轉(zhuǎn)權(quán)1，給關(guān)聯(lián)的4－，5－面轉(zhuǎn)權(quán)

R1.3:若v關(guān)聯(lián)2個(gè)3－面，則v給關(guān)聯(lián)的3－面轉(zhuǎn)權(quán)1，給關(guān)聯(lián)的4－面轉(zhuǎn)權(quán)，給關(guān)聯(lián)的5－面轉(zhuǎn)權(quán)

下面證明?v∈V(G)，w'(v)≥0.

1)d(v)=4或d(v)=5.

對(duì)于4－點(diǎn)v，由于圖G不含7－圈且不含相鄰的4－圈，則v最多關(guān)聯(lián)2個(gè)3－面.若v不關(guān)聯(lián)3－面，則由R0.1知，w'(v)≥2×4－6－1 2×4=0.若v僅關(guān)聯(lián)1個(gè)3－面，則v最多再關(guān)聯(lián)1個(gè)4－面或3個(gè)5－面，且v關(guān)聯(lián)1個(gè)4－面時(shí)，v最多再關(guān)聯(lián)1個(gè)5－面，進(jìn)一步由R0.2知，

若v關(guān)聯(lián)2個(gè)3－面，則v不再關(guān)聯(lián)5－面且v最多再關(guān)聯(lián)1個(gè)4－面，進(jìn)一步由R0.3知，

類(lèi)似地，對(duì)于5－點(diǎn)v，由于圖G不含7－圈且不含相鄰的4－圈，則v最多關(guān)聯(lián)3個(gè)3－面.若v不關(guān)聯(lián)3－面，則由R1.1知，

若v僅關(guān)聯(lián)1個(gè)3－面，則v最多再關(guān)聯(lián)2個(gè)4－面或4個(gè)5－面，且當(dāng)v關(guān)聯(lián)2個(gè)4－面時(shí)，v不再關(guān)聯(lián)5－面，當(dāng)v關(guān)聯(lián)1個(gè)4－面時(shí)，v最多再關(guān)聯(lián)2個(gè)5－面，進(jìn)一步由R1.2知，

若v關(guān)聯(lián)2個(gè)3－面，則v最多再關(guān)聯(lián)1個(gè)4－面和2個(gè)5－面，進(jìn)一步由R1.3知，

若v關(guān)聯(lián)3個(gè)3－面，則v不再關(guān)聯(lián)4－面和5－面，進(jìn)一步由R1.4知，

2)d(v)=6，w(v)=6.

由于圖G不含7－圈且不含相鄰的4－圈，所以v最多關(guān)聯(lián)4個(gè)3－面.若v關(guān)聯(lián)4個(gè)3－面，則v不再關(guān)聯(lián)4－面和5－面，進(jìn)一步由R2知，

若v關(guān)聯(lián)3個(gè)3－面，則v最多關(guān)聯(lián)1個(gè)4－面或1個(gè)5－面，從而

若v關(guān)聯(lián)2個(gè)3－面，則v最多關(guān)聯(lián)2個(gè)4－面或4個(gè)5－面，且當(dāng)v關(guān)聯(lián)2個(gè)4－面時(shí)，v不再關(guān)聯(lián)5－面，從而

若v關(guān)聯(lián)1個(gè)3－面，則v最多關(guān)聯(lián)2個(gè)4－面或5個(gè)5－面，且當(dāng)v關(guān)聯(lián)2個(gè)4－面時(shí)，v最多再關(guān)聯(lián)1個(gè)5－面，從而

若v不關(guān)聯(lián)3－面，則與v關(guān)聯(lián)的都是4+－面，從而w'(v)≥6－1×6=0.

3)d(v)=7，w(v)=8.

由于圖G不含7－圈且不含相鄰的4－圈，所以v最多關(guān)聯(lián)4個(gè)3－面.若v最多關(guān)聯(lián)2個(gè)3－面，則由R2知，若v關(guān)聯(lián)3個(gè)3－面，則v最多關(guān)聯(lián)2個(gè)4－面，進(jìn)一步由R2知，

若v關(guān)聯(lián)4個(gè)3－面，則v最多關(guān)聯(lián)1個(gè)4－面，且不再關(guān)聯(lián)5－面，進(jìn)一步由R2知，

4)d(v)=8，w(v)=10.

由于圖G不含7－圈且不含相鄰的4－圈，所以v最多關(guān)聯(lián)5個(gè)3－面.若v最多關(guān)聯(lián)4個(gè)3－面，則由R2知，.若v關(guān)聯(lián)5個(gè)3－面，則v不再關(guān)聯(lián)4－面或5－面，進(jìn)一步由R2知，

5)d(v)≥9，w(v)≥12.

綜上所述，即得?v∈V(G)，w'(v)≥0.

下面證明?f∈F(G)，w'(f)≥0.由于圖G不含7－圈且不含相鄰的4－圈及δ(G)≥4，可以得到如下斷言:

斷言1 4－面最多關(guān)聯(lián)1個(gè)壞4－點(diǎn).

斷言2 好面為8+－面且好面最多關(guān)聯(lián)個(gè)壞4－點(diǎn).

1)d(f)=3，w(f)=－3.

由R0，R1和R2知，?v∈V(G)，v給關(guān)聯(lián)的3－面轉(zhuǎn)權(quán)至少是1，則

2)d(f)=4，w(f)=－2.

由于圖G不含7－圈且不含相鄰的4－圈，所以4－面最多關(guān)聯(lián)2個(gè)3－面.若f不是壞4－面，則與f關(guān)聯(lián)的4－點(diǎn)最多關(guān)聯(lián)1個(gè)3－面，與f關(guān)聯(lián)的5－點(diǎn)最多關(guān)聯(lián)2個(gè)3－面，由R0，R1和R2知，與f關(guān)聯(lián)的每個(gè)頂點(diǎn)v給f轉(zhuǎn)權(quán)至少是，從而

若f是一個(gè)壞4－面，則由斷言1、斷言2和R3知，好面通過(guò)壞4－點(diǎn)給壞4－面轉(zhuǎn)權(quán)至少是，而對(duì)于f中另外3個(gè)頂點(diǎn)中的每個(gè)頂點(diǎn)v，均不出現(xiàn)R0.3和R1.4的情形，故每個(gè)頂點(diǎn)v給f轉(zhuǎn)權(quán)至少是，從而

3)d(f)=5，w(f)=－1.

由于圖G不含7－圈且δ(G)≥4，所以f最多相鄰1個(gè)3－面，f中至少有4個(gè)頂點(diǎn)不出現(xiàn)R0.3和R1.4的情形，則由R0，R1和R2知，f中的這些頂點(diǎn)v給關(guān)聯(lián)的5－面轉(zhuǎn)權(quán)至少是，從而

4)d(f)=6，w(f)=0.

由R0～R3知，6－面沒(méi)有發(fā)生權(quán)轉(zhuǎn)移，故w'(f)=w(f)=0.

5)d(f)≥8，w(f)≥2.

由斷言2知，8+－面最多關(guān)聯(lián)個(gè)壞4－點(diǎn)，由R3可得，

綜上，當(dāng)G是2－連通時(shí)，對(duì)每個(gè)x∈V(G)∪F(G)，w'(x)≥0.因此，

矛盾.

下面假設(shè)G不是2－連通的，這意味著G有割點(diǎn).設(shè)B是一個(gè)僅包含1個(gè)割點(diǎn)ω的塊，則B是2－連通的，且dB(ω)≥2.因此，B的每個(gè)面都是一個(gè)圈，B的每個(gè)頂點(diǎn)v關(guān)聯(lián)dB(v)個(gè)不同的面.顯然，B不含7－圈且不含相鄰4－圈，因此B不含7－面且不含相鄰4－圈.下面在B=(V(B)，E(B))中考慮權(quán)轉(zhuǎn)移.設(shè)f0是B的外部面，則由性質(zhì)1、性質(zhì)2和性質(zhì)3知，?v∈V(B)－{ω}，dB(v)≥4.根據(jù)連通平面圖的Euler公式|V|+|F|－|E|=2及度和公式，有

對(duì)于任意的x∈V(B)∪F(B)，構(gòu)造一個(gè)權(quán)函數(shù)w(x)，其中當(dāng)v∈V(B)時(shí)，w(v)=2dB(v)－6，當(dāng)f∈F(B)時(shí)，w(f)=dB(f)－6.

在B中按以下規(guī)則進(jìn)行權(quán)轉(zhuǎn)移:

R4:頂點(diǎn)ω給每個(gè)除f0外的關(guān)聯(lián)的3－，4－，5－面轉(zhuǎn)權(quán)

R5:面f0通過(guò)壞4－點(diǎn)給壞4－面轉(zhuǎn)權(quán)

R6:對(duì)于v∈V(B)－{ω}，f∈F(B)－{f0}，根據(jù)G是2－連通時(shí)的轉(zhuǎn)權(quán)規(guī)則R0～R3進(jìn)行.

容易發(fā)現(xiàn)，在完成R4～R6后，與前面一樣可以驗(yàn)證:?x∈V(B)∪F(B)－{ω，f0}，都有w'(x)≥0.下面考慮ω和f0，根據(jù)R4與dB(ω)≥2，有

根據(jù)R5與dB(f0)≥3，有

因此，

矛盾.定理1證畢.

2 結(jié)語(yǔ)

本文討論了沒(méi)有7－圈的連通平面圖的BB－染色問(wèn)題，證明了沒(méi)有7－圈且不含相鄰4－圈的連通平面圖G，存在G的一棵生成樹(shù)T，使得(G，T)是BB－4－可染的.那么，筆者認(rèn)為，對(duì)于沒(méi)有7－圈的連通平面圖G，同樣也存在G的一棵生成樹(shù)T，使得(G，T)是BB－4－可染的.對(duì)此，筆者將作進(jìn)一步的研究.

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

［2］Akiyama J，Baskoro E T，Kano M.Combinatorial geometry and graph theory［M］.Berlin:Springer，2005:65－79.

［3］Broersma H，F(xiàn)omin F V，Golovach P A，et al.Backbone coloring for graphs:tree and path backbone［J］.J Graph Theory，2007，55(2):137－152.

［4］Broersma H，F(xiàn)ujisawa J，Marchal L，et al.λ－backbone coloring along pairwise disjoint stars and matchings［J］.Discrete Math，2009，309(18): 5596－5609.

［5］Broersma H，Marchal L，Paulusma D，et al.Backbone coloring along stars and matchings in split graphs:their span is close to the chromatic number［J］.Discuss Math Graph Theory，2009，29(1):143－162.

［6］Wang Weifang，Bu Yuehua，Montassier M，et al.On backbone coloring of graphs［J］.J Comb Optim，2012，23(1):79－93.

［7］Bu Yuehua，Zhang Shuiming.Backbone coloring for C5－free planar graphs［J］.J Math Study，2010，43(4):315－321.

［8］卜月華，張水明.沒(méi)有4－圈的平面圖的BB－染色［J］.中國(guó)科學(xué):A輯數(shù)學(xué)，2011，41(2):197－206.

［9］Bu Yuehua，Li Yulin.Backbone coloring of planar graphs without special circles［J］.Theoret Comput Sci，2011，412(46):6464－6468.

(責(zé)任編輯 陶立方)

The backbone coloring of planar graphs without 7-cycles

BU Yuehua， BAO Xudong

(College of Mathematics，Physics and Information Engineering，Zhejiang Normal University，Jinhua Zhejiang 321004，China)

The problem of backbone coloring of connected planar graphs without 7－cycles was studied.By using the discharging technique，it was proved that if G is a connected planar graph without 7－cycles and adjacent 4－cycles，then there would have a spanning tree T of G such that(G，T)is BB－4－colorable.The result generalized the sufficient condition for the planar graphs of BB－4－colorable.

planar graph;backbone coloring;spanning tree;cycle

O157.5

A

1001－5051(2015)01－0028－06

?:2014－04－20;

2014－06－12

國(guó)家自然科學(xué)基金資助項(xiàng)目(11271334)

卜月華(1960－)，男，浙江東陽(yáng)人，教授，博士.研究方向:組合數(shù)學(xué)與圖論.

10.16218/j.issn.1001－5051.2015.01.005