沒有7－圈的平面圖的BB－染色*

卜月華， 鮑旭東

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

沒有7－圈的平面圖的BB－染色*

卜月華， 鮑旭東

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

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

平面圖;BB－染色;生成樹;圈

0 引言

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

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

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

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

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

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

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

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

1 定理1的證明

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

下面根據G的極小性，給出G的幾個結構性質和定義.

定義1 若一個4－點v關聯2個3－面和1個4－面，且這2個3－面不相鄰，則稱此4－點為壞4－點，此4－面為壞4－面(如圖1所示的f1)，與壞4－面不相鄰且相交于頂點v的面稱為好面(如圖1所示的f2).

圖1 壞4－點v，壞4－面f1，好面f2

圖G具有以下結構性質:

性質1［8］圖G不含1－點.

性質2［8］圖G不含2－點.

性質3［8］圖G不含3－點.

下面運用權轉移方法完成定理1的證明.

先假設平面圖G=(V，E，F)是2－連通的，則G的每個面的邊界都是一個圈，G中每個頂點v關聯d(v)個面.根據連通平面圖的Euler公式|V|+|F|－|E|=2及度和公式，有

對于任意的x∈V(G)∪F(G)，構造一個權函數w(x)，其中當v∈V(G)時，w(v)=2d(v)－6，當f∈F(G)時，w(f)=d(f)－6，則

下面根據G的結構性質，在保持總的權和不變的情況下，對G中的點和面按照一定的權轉移規則進行轉權，經過權轉移后得到一個新的權函數w'(x).將證明對于任意的x∈V(G)∪F(G)，都有w'(x)≥0，從而得到如下矛盾:

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

下面給出如下權轉移規則:

R0:d(v)=4.

R0.1:若v不關聯3－面，則v給關聯的4+－面轉權

R0.2:若v關聯一個3－面，則v給關聯的3－面轉權1，給關聯的4－面轉權，給關聯的5－面轉權

R0.3:若v關聯2個3－面，則v給關聯的3－面轉權1.

R1:d(v)=5.

R1.1:若v不關聯3－面，則v給關聯的4+－面轉權

R1.2:若v關聯1個3－面，則v給關聯的3－面轉權1，給關聯的4－，5－面轉權

R1.3:若v關聯2個3－面，則v給關聯的3－面轉權1，給關聯的4－面轉權，給關聯的5－面轉權

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

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

對于4－點v，由于圖G不含7－圈且不含相鄰的4－圈，則v最多關聯2個3－面.若v不關聯3－面，則由R0.1知，w'(v)≥2×4－6－1 2×4=0.若v僅關聯1個3－面，則v最多再關聯1個4－面或3個5－面，且v關聯1個4－面時，v最多再關聯1個5－面，進一步由R0.2知，

若v關聯2個3－面，則v不再關聯5－面且v最多再關聯1個4－面，進一步由R0.3知，

類似地，對于5－點v，由于圖G不含7－圈且不含相鄰的4－圈，則v最多關聯3個3－面.若v不關聯3－面，則由R1.1知，

若v僅關聯1個3－面，則v最多再關聯2個4－面或4個5－面，且當v關聯2個4－面時，v不再關聯5－面，當v關聯1個4－面時，v最多再關聯2個5－面，進一步由R1.2知，

若v關聯2個3－面，則v最多再關聯1個4－面和2個5－面，進一步由R1.3知，

若v關聯3個3－面，則v不再關聯4－面和5－面，進一步由R1.4知，

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

由于圖G不含7－圈且不含相鄰的4－圈，所以v最多關聯4個3－面.若v關聯4個3－面，則v不再關聯4－面和5－面，進一步由R2知，

若v關聯3個3－面，則v最多關聯1個4－面或1個5－面，從而

若v關聯2個3－面，則v最多關聯2個4－面或4個5－面，且當v關聯2個4－面時，v不再關聯5－面，從而

若v關聯1個3－面，則v最多關聯2個4－面或5個5－面，且當v關聯2個4－面時，v最多再關聯1個5－面，從而

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

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

由于圖G不含7－圈且不含相鄰的4－圈，所以v最多關聯4個3－面.若v最多關聯2個3－面，則由R2知，若v關聯3個3－面，則v最多關聯2個4－面，進一步由R2知，

若v關聯4個3－面，則v最多關聯1個4－面，且不再關聯5－面，進一步由R2知，

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

由于圖G不含7－圈且不含相鄰的4－圈，所以v最多關聯5個3－面.若v最多關聯4個3－面，則由R2知，.若v關聯5個3－面，則v不再關聯4－面或5－面，進一步由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－面最多關聯1個壞4－點.

斷言2 好面為8+－面且好面最多關聯個壞4－點.

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

由R0，R1和R2知，?v∈V(G)，v給關聯的3－面轉權至少是1，則

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

由于圖G不含7－圈且不含相鄰的4－圈，所以4－面最多關聯2個3－面.若f不是壞4－面，則與f關聯的4－點最多關聯1個3－面，與f關聯的5－點最多關聯2個3－面，由R0，R1和R2知，與f關聯的每個頂點v給f轉權至少是，從而

若f是一個壞4－面，則由斷言1、斷言2和R3知，好面通過壞4－點給壞4－面轉權至少是，而對于f中另外3個頂點中的每個頂點v，均不出現R0.3和R1.4的情形，故每個頂點v給f轉權至少是，從而

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

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

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

由R0～R3知，6－面沒有發生權轉移，故w'(f)=w(f)=0.

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

由斷言2知，8+－面最多關聯個壞4－點，由R3可得，

綜上，當G是2－連通時，對每個x∈V(G)∪F(G)，w'(x)≥0.因此，

矛盾.

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

對于任意的x∈V(B)∪F(B)，構造一個權函數w(x)，其中當v∈V(B)時，w(v)=2dB(v)－6，當f∈F(B)時，w(f)=dB(f)－6.

在B中按以下規則進行權轉移:

R4:頂點ω給每個除f0外的關聯的3－，4－，5－面轉權

R5:面f0通過壞4－點給壞4－面轉權

R6:對于v∈V(B)－{ω}，f∈F(B)－{f0}，根據G是2－連通時的轉權規則R0～R3進行.

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

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

因此，

矛盾.定理1證畢.

2 結語

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

［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，Fomin 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，Fujisawa 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］卜月華，張水明.沒有4－圈的平面圖的BB－染色［J］.中國科學:A輯數學，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.

(責任編輯 陶立方)

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

國家自然科學基金資助項目(11271334)

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

10.16218/j.issn.1001－5051.2015.01.005