圍長至少為5的平面圖的injective染色*

卜月華, 葉飄飄

(1.浙江師范大學 數理與信息工程學院,浙江 金華 321004;2.浙江師范大學 行知學院,浙江 金華 321004)

?

圍長至少為5的平面圖的injective染色*

卜月華1,2, 葉飄飄1

(1.浙江師范大學 數理與信息工程學院,浙江 金華 321004;2.浙江師范大學 行知學院,浙江 金華 321004)

通過構造一個(Δ+3)-臨界圖G,運用權轉移的方法證明了該圖G不存在.同時，用反證法證明了：對于圍長至少為5的平面圖G,若Δ(G)≥30,則χi(G)≤Δ+3.這個結論改進了現有的一個結果.

平面圖;圍長;injective染色;面

0 引 言

本文僅考慮有限簡單圖.對于一個平面圖G,把它的頂點集、邊集、面集、最大度、最小度、圍長及圖G中u,v間的距離分別記作V(G),E(G),F(G),Δ(G),δ(G),g(G)和dG(u,v).對于圖G的一個頂點v,若d(v)=k(或d(v)≥k,或d(v)≤k),則稱v為一個k-點(或k+-點,或k--點).對平面圖的面也可以類似定義.?f∈F(G),記B(f)為面f的邊界跡.若u1u2…un在B(f)上按順時針排列,則面f記為f=[u1u2…un].圍長g(G)表示圖G中最短圈的長度.

圖G的正常頂點染色是指對圖G的每個頂點分配一種顏色,使得相鄰的2個頂點染不同色,其所需的最少顏色數稱為圖G的色數,記為χ(G).圖G的injectivek-染色是指映射c:V(G)→{1,2,…,k},使得有公共鄰點的2個頂點u,v滿足c(u)≠c(v).若圖G有一個injectivek-染色,則稱圖G是injectivek-可染的,并稱χi(G)=min{k|G是injectivek-可染的}為圖G的injective色數.

Injective染色是由Hahn等[1]提出,并且證明了對任意的平面圖G都有Δ(G)≤χi(G)≤(Δ(G))2-Δ(G)+1.隨后,人們對平面圖的injective染色問題展開了一系列的研究.Doyon等[2]證明了:對任意圍長為g(G)且最大度為Δ的平面圖G,有:若g(G)≥7,則χi(G)≤Δ+3;若g(G)≥6,則χi(G)≤Δ+4;若g(G)≥5,則χi(G)≤Δ+8.文獻[2-5]研究了稀疏圖和平面圖的injective色數的上界問題.文獻[6]證明了:對于圍長g(G)≥6的平面圖G,χi(G)≤Δ+3;若Δ≥9,則χi(G)≤Δ+2;若Δ≥17,則χi(G)≤Δ+1.文獻[7]證明了:對于圍長為g(G)≥5的平面圖G,χi(G)≤Δ+6;若Δ≥35,則χi(G)≤Δ+3.

問題1 是否存在一個整數M,使得g(G)≥5且Δ≥M的平面圖G是injective (Δ+1)-可染的？

本文研究圍長為g(G)≥5的平面圖G的injective染色,證明了下面這個定理:

定理1 若圖G是g(G)≥5,Δ(G)≥30的平面圖,則χi(G)≤Δ(G)+3.

1 臨界圖的構型

若圖G不是injectivek-可染,但是它的任意真子圖都是injectivek-可染,則稱這樣的圖G為k-臨界圖.接下來將研究k-臨界圖的一些性質.

設c是圖G的injective染色,頂點v所染的顏色記作c(v),對G的一個頂點子集S,所染的顏色集記作c(S)={c(v) | v∈S}.

以下是k-臨界圖G(k≥Δ+1)的一些性質,其證明可見文獻[6].

性質1 設圖G是k-臨界圖,其中k≥Δ+1,uv∈E(G).若D(u)≤k-1+d(u),則D(v)≥k+d(v).

性質2 設圖G是(Δ+t)-臨界圖,其中t≥1,則G不包含相鄰2-點且δ(G)≥2.

性質3 設圖G是(Δ+t)-臨界圖,其中t≥1,v是2-點,記N(v)={v1,v2}.若D(v)≤Δ+t+1,則?i∈{1,2},D(vi)≥Δ+t+d(vi).

性質4 設圖G是(Δ+t)-臨界圖,其中t≥1,v是3-點,記N(v)={v1,v2,v3}.若D(v)≤Δ+t+2,則?i∈{1,2,3},D(vi)≥Δ+t+d(vi).

由性質4可知,輕3(0)-點與輕3(0)-點不相鄰.

2 定理1的證明

下面用反證法證明定理1.若定理1的結論不成立,則存在平面圖 G′,使g(G′)≥5,Δ(G′)≥30,但χ(G′)>Δ(G′)+3.令圖G是一個滿足Δ(G)≤Δ(G′)=Δ,g(G)≥5,χ(G)>Δ+3且|E(G)|+|V(G)|最小的平面圖,則圖G是(Δ+3)-臨界圖.顯然,圖G是連通圖且δ(G)≥2.

記ε=1/5.用權轉移方法證明G是不存在的.

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

這個矛盾說明G不存在,從而定理1是成立的.

權轉移分2步進行.第1步:對?x∈V∪F,設置初始權為w(x).運用一些轉權規則,將證明除一些5-點、6-點外的任意頂點和面得到的新權w′(x)≥0.第 2 步:將對于這些權小于零的頂點定義新的轉權規則,得到的新權記為w*(x)，并將證明w*(x)≥0.

定義以下權轉移規則:

R1:3≤d(v)≤9的點v給相鄰的輕2-點轉權1;

R3:若4≤d(v)≤9,則v給相鄰的3(1)-點轉權ε;

記 f是G的k-面.因為k≥5,所以對?f∈F(G),w′(f)=d(f)-5≥0.

對于頂點v,設d(v)=k,則由性質2知 k≥2.

3)k=4,w(v)=1.因為d(v)=4,所以與v相鄰的每個2-點都是輕2-點.

在運用第1次權轉移規則后,對?x∈V(G)∪F(G),除了一些5-點和6-點外,其余的頂點和面都有非負的權值.稱這些權值可能為負的5-點和6-點為壞5-點和壞6-點;稱權值非負的頂點為好點.綜上討論,存在4種可能的壞5-點和壞6-點.

對uv∈E(G),若d(u)≥10,d(v)≥10,則稱uv為特殊邊.

第2次權轉移規則R6～R8:

R7:每個2≤k≤9的k-點v將多余的權值平均轉給每個關聯面;

R8:通過R6,R7轉權后,每個5+-面 f將多余的權值平均轉給面 f上可能的壞5-點和壞6-點.

運用第2次轉權規則之后,把?x∈V(G)∪F(G)的新權記為w*(x).

反證法 若4≤d(w1)≤5,則可設d(u1)=2.由G的極小性知,G-vw有一個(Δ+3)-injective染色c.先擦去v和w的顏色.若|c(N2(v))|≤Δ+2,則可以把c延拓到整個圖G.因為w的禁用色至多是8,所以w可以被正常染好.否則,設 |c(N2(v))|≥Δ+3.因為|N2(v)|=Δ+3,所以|c(N2(v))|=Δ+3.考慮 u1,易知擦去v和w的顏色之后,|c(N2(u1))|≤Δ+1,可以用c(u1)染v,再把u1染好,最后染w.這樣,c就成為G的一個(Δ+3)-injective染色.與假設矛盾.斷言1證畢.

下面分4種情形討論壞5-點和壞6-點最終的權.

若v不關聯6+-面,則v恰好關聯5個5-面.有{w1x1,x1y1,y1z1,z1u2,u1w1}?E(G),其中u1,u2∈N(u).記 f1=[uvww1u1],f2=[zvuu2z1],f3=[yvzz1y1],f4=[xvyy1x1].若d(u1)≥10,則uu1是特殊邊,由R6 知,面 f1至少可以從u,u1獲得權1.因為v是面 f1中唯一的壞5-點或壞6-點, 所以由R8 知, v從面 f1獲得權 1.因此,w*(v)≥w′(v)+1>0.類似地,若d(u2)≥10,則 w*(v)≥0.下面僅考慮d(u1)≤9,d(u2)≤9.

②w1和z1中至少有1個為9--點,不妨設3≤d(z1)≤9.因為z是輕2-點,所以由性質3知,D(z1)≥Δ+3+d(z1).

通過2次權轉移就檢驗了對任意x∈V(G)∪F(G),都有w*(x)≥0,從而得到矛盾.定理1證畢.

3 結 語

本文討論了圍長至少為5的平面圖的injective染色問題,證明了:若圖G是 g(G)≥5,Δ(G)≥30的平面圖,則χi(G)≤Δ(G)+3.根據文獻[7]的結論和本文結果,下面這個問題是有意義的,即:對于g(G)≥5的平面圖G,探討最小的正整數Δ0,使得當Δ(G)≥Δ0時,有χi(G)≤Δ(G)+3.

[1]Hahn G,Kratochvíl J,Sirá J,et al.On the injective chromatic number of graphs[J].Discrete Math,2002,256(1/2):179-192.

[2]Doyon A,Hahn G,Raspaud A.Some bounds on the injective chromatic number of graphs[J].Discrete Math,2012,310(3):585-590.

[3]Cranston D,Kim S,Yu G.Injective colorings of graphs with low average degree[J].Algorithmica,2010,60(3):553-568.

[4]Cranston D,Kim S,Yu G.Injective colorings of sparse graphs[J].Discrete Math,2010,310(21):2965-2973.

[5]Bu Y,Chen D,Raspaud A,et al.Injective coloring of planar graphs[J].Discrete Appl Math,2009,157(4):663-672.

[6]Dong W,Lin W.Injective coloring of planar graphs with girth 6[J].Discrete Math,2013,313(12):1302-1311.

[7]Dong W,Lin W.Injective coloring of plane graphs with girth 5[J].Discrete Math,2014,315/316(12):120-127.

(責任編輯 陶立方)

Injective coloring of planar graphs with grith 5

BU Yuehua1,2, YE Piaopiao1

(1.CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China; 2.XingzhiCollege,ZhejiangNormalUniversity,Jinhua321004,China)

LetGbe a plane graph withg(G)≥5 andχi(G) be the injective chromatic number ofG. It was improved some known results by proving thatχi(G)≤Δ+3 whenΔ(G)≥30. The result was obtained by contradiction: LetGbe a (Δ+3)-critical graph, a discharging procedure was applied to the proof by showing thatGcould not exist.

planar graph; grith; injective coloring; face

10.16218/j.issn.1001-5051.2017.01.001

2016-04-23；

2016-05-29

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

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

O157.5

A

1001-5051(2017)01-0001-08