卜月華,王 超

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

?

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

卜月華1,2,王 超1

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

研究了圍長至少為5的平面圖的injective列表染色問題.通過分析極小反例的結(jié)構(gòu)性質(zhì)并利用權(quán)轉(zhuǎn)移方法,證明了圍長至少為5且最大度至少為12的平面圖G的injective列表色數(shù)不超過Δ(G)+4.此結(jié)果進(jìn)一步拓展了平面圖關(guān)于injective色數(shù)的Lu?ar 猜想成立的充分條件.

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

0 引 言

圖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染色問題展開了一系列的研究.定理1給出了在最大平均度的條件限制下的結(jié)果.

定理1 對(duì)于一個(gè)圖 G.

另外,利用圖的圍長和最大度作為限制條件,有以下結(jié)果:

定理2 設(shè)圖G是一個(gè)g(G)≥g′且Δ(G)≥D的平面圖.

1)若(g′,D)∈{(13,4),(12,5),(10,6),(8,10),(7,16)},則χi(G)=Δ(G)[4-5];

2)若(g′,D)∈{(11,1),(9,4),(8,5),(6,17)},則χi(G)≤Δ(G)+1[5-7];

3)若(g′,D)∈{(6,8)},則χi(G)≤Δ(G)+2[7].

2009年,Lu?ar等[8]提出了如下的猜想:

本文將證明下面的定理:

1 定理3的證明

對(duì)于一個(gè)i-點(diǎn)v(3≤i≤5),若v至多與2個(gè)3+-點(diǎn)相鄰,則稱v為壞i-點(diǎn).

性質(zhì)1

1)δ(G)≥2;

2)若uv∈E(G),則max{SG(u),SG(v)}≥Δ+4;

3)G中無相鄰的2-點(diǎn);

4)壞5-點(diǎn)不與壞i-點(diǎn)(i=3,4)相鄰;

5)52-點(diǎn)v至多與1個(gè)壞3-點(diǎn)或1個(gè)壞4-點(diǎn)相鄰,且v不同時(shí)與壞3-點(diǎn)和壞4-點(diǎn)相鄰.

3)若u,v是2個(gè)相鄰的2-點(diǎn),則有SG(u)≤Δ和SG(v)≤Δ,這與性質(zhì)1的2)矛盾.

4)假設(shè)壞5-點(diǎn)相鄰壞4-點(diǎn),如圖1(a)所示.v是壞5-點(diǎn),v4是壞4-點(diǎn).根據(jù)G的極小性知,G-vv4有一個(gè)injectiveL-染色,再抹去v,v4,v42,v43,v1,v2,v3的顏色,此時(shí)它們的可用色分別至少為1,2,4,4,4,4,4.顯然,可以將它們依次染好(注:若其中有2個(gè)頂點(diǎn)有公共鄰點(diǎn),則這2個(gè)頂點(diǎn)的可用色各增加1,下同),這樣便得到了G的一個(gè)injectiveL-染色(如果v4是壞3-點(diǎn),那么在改染的時(shí)候,它將會(huì)有更多的可用色).矛盾.

5)只需證明52-點(diǎn)不與2個(gè)壞4-點(diǎn)相鄰,如圖1(b)所示.v是52-點(diǎn),v3,v4是壞4-點(diǎn).根據(jù)G的極小性知,G-vv4有一個(gè)injectiveL-染色.再抹去v,v3,v4,v32,v33,v42,v43,v1,v2的顏色,它們的可用色分別至少為1,2,2,4,4,4,4,4,4.顯然,可以將它們依次染好,這樣便得到了G的一個(gè)injectiveL-染色.矛盾.

圖1 性質(zhì)1中的4)和5)的2個(gè)構(gòu)型

對(duì)任意x∈V∪F，構(gòu)造一個(gè)權(quán)函數(shù)μ(x)，其中當(dāng)v∈V時(shí)，μ(v)=-5，當(dāng)f∈F時(shí)，μ(f)=d(f)-5，則有=-10．下面根據(jù)G的結(jié)構(gòu)性質(zhì)，在保持總權(quán)和不變的情況下，對(duì)G中的點(diǎn)和面的權(quán)按一定規(guī)則進(jìn)行轉(zhuǎn)移，得到一個(gè)新的權(quán)函數(shù)μ'(x)．下面將證明:對(duì)任意x∈V∪F，都有μ'(x)≥0．從而得出如下矛盾:

該矛盾說明G不存在,從而定理3是成立的.

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

R0:3+-點(diǎn)給相鄰的2-點(diǎn)轉(zhuǎn)權(quán)1.

R1:設(shè)v是一個(gè)3-點(diǎn),uv∈E(G).

R2:設(shè)v是一個(gè)4-點(diǎn),uv∈E(G).

下面將檢驗(yàn)μ′(v)≥0,?v∈V(G).

1)d(v)=2,μ(v)=-2.由性質(zhì)1的3)及R0知,μ′(v)≥-2+1×2=0.

3)d(v)=4,μ(v)=1.根據(jù)性質(zhì)1的2)知,n3+(v)≥2.

接下來檢驗(yàn)μ′(f)≥0,?f∈F(G).

這樣就檢驗(yàn)了對(duì)任意x∈V∪F,都有μ′(x)≥0,從而得到如下矛盾的式子:

定理 3 證畢.

2 結(jié) 語

本文討論了圍長至少為5的平面圖的injective列表染色問題,并證明了圍長至少為5且最大度至少為12的平面圖G的injective列表色數(shù)不超過Δ(G)+4.對(duì)此,筆者認(rèn)為,若對(duì)平面圖G的最大度作進(jìn)一步的限制(如 Δ(G)≥10),對(duì)G的結(jié)構(gòu)性質(zhì)再作更加細(xì)致的刻畫,會(huì)有同樣的結(jié)果;同時(shí),在同樣的最大度條件限制下,估計(jì)會(huì)有injective列表色數(shù)不超過Δ(G)+3.為此,我們將進(jìn)行更深層的研究.

[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]Cranston D W,Kim S J,Yu G.Injective colorings of graphs with low average degree[J].Algorithmica,2010,60(3):553-568.

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

[4]Borodin O V,Ivanova A O.Injective (Δ+1)-coloring of planar graphs with grith 6[J].Siberian Math J,2011,52(1):23-29.

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

[6]Bu Y,Lu K.List injective coloring of planar graphs with grith 5,6,8[J].Discrete App Math,2013,161(10/11):1367-1377.

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

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

List injective coloring of planar graphs with grith 5

BU Yuehua,1,2WANG Chao1

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

planar graph; grith; list injective coloring; face

10.16218/j.issn.1001-5051.2016.01.002

??2015-06-23；

2015-09-11

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

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

O157.5

A

1001-5051(2016)01-006-07