圍長(zhǎng)至少為5的平面圖的injective染色*

卜月華, 葉飄飄

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

?

圍長(zhǎng)至少為5的平面圖的injective染色*

卜月華1,2, 葉飄飄1

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

通過構(gòu)造一個(gè)(Δ+3)-臨界圖G,運(yùn)用權(quán)轉(zhuǎn)移的方法證明了該圖G不存在.同時(shí)，用反證法證明了：對(duì)于圍長(zhǎng)至少為5的平面圖G,若Δ(G)≥30,則χi(G)≤Δ+3.這個(gè)結(jié)論改進(jìn)了現(xiàn)有的一個(gè)結(jié)果.

平面圖;圍長(zhǎng);injective染色;面

0 引 言

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

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

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

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

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

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

1 臨界圖的構(gòu)型

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

設(shè)c是圖G的injective染色,頂點(diǎn)v所染的顏色記作c(v),對(duì)G的一個(gè)頂點(diǎn)子集S,所染的顏色集記作c(S)={c(v) | v∈S}.

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

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

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

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

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

由性質(zhì)4可知,輕3(0)-點(diǎn)與輕3(0)-點(diǎn)不相鄰.

2 定理1的證明

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

記ε=1/5.用權(quán)轉(zhuǎn)移方法證明G是不存在的.

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

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

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

定義以下權(quán)轉(zhuǎn)移規(guī)則:

R1:3≤d(v)≤9的點(diǎn)v給相鄰的輕2-點(diǎn)轉(zhuǎn)權(quán)1;

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

記 f是G的k-面.因?yàn)閗≥5,所以對(duì)?f∈F(G),w′(f)=d(f)-5≥0.

對(duì)于頂點(diǎn)v,設(shè)d(v)=k,則由性質(zhì)2知 k≥2.

3)k=4,w(v)=1.因?yàn)閐(v)=4,所以與v相鄰的每個(gè)2-點(diǎn)都是輕2-點(diǎn).

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

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

第2次權(quán)轉(zhuǎn)移規(guī)則R6～R8:

R7:每個(gè)2≤k≤9的k-點(diǎn)v將多余的權(quán)值平均轉(zhuǎn)給每個(gè)關(guān)聯(lián)面;

R8:通過R6,R7轉(zhuǎn)權(quán)后,每個(gè)5+-面 f將多余的權(quán)值平均轉(zhuǎn)給面 f上可能的壞5-點(diǎn)和壞6-點(diǎn).

運(yùn)用第2次轉(zhuǎn)權(quán)規(guī)則之后,把?x∈V(G)∪F(G)的新權(quán)記為w*(x).

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

下面分4種情形討論壞5-點(diǎn)和壞6-點(diǎn)最終的權(quán).

若v不關(guān)聯(lián)6+-面,則v恰好關(guān)聯(lián)5個(gè)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獲得權(quán)1.因?yàn)関是面 f1中唯一的壞5-點(diǎn)或壞6-點(diǎn), 所以由R8 知, v從面 f1獲得權(quán) 1.因此,w*(v)≥w′(v)+1>0.類似地,若d(u2)≥10,則 w*(v)≥0.下面僅考慮d(u1)≤9,d(u2)≤9.

②w1和z1中至少有1個(gè)為9--點(diǎn),不妨設(shè)3≤d(z1)≤9.因?yàn)閦是輕2-點(diǎn),所以由性質(zhì)3知,D(z1)≥Δ+3+d(z1).

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

3 結(jié) 語

本文討論了圍長(zhǎng)至少為5的平面圖的injective染色問題,證明了:若圖G是 g(G)≥5,Δ(G)≥30的平面圖,則χi(G)≤Δ(G)+3.根據(jù)文獻(xiàn)[7]的結(jié)論和本文結(jié)果,下面這個(gè)問題是有意義的,即:對(duì)于g(G)≥5的平面圖G,探討最小的正整數(shù)Δ0,使得當(dāng)Δ(G)≥Δ0時(shí),有χ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.

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

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

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

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

O157.5

A

1001-5051(2017)01-0001-08