围长至少为5的平面图的injective列表染色*

卜月华,王 超

(1.浙江师范大学 数理与信息工程学院,浙江 金华 321004;2.浙江师范大学 行知学院，浙江 金华 321004)



围长至少为5的平面图的injective列表染色*

卜月华1,2,王 超1

(1.浙江师范大学 数理与信息工程学院,浙江 金华 321004;2.浙江师范大学 行知学院，浙江 金华 321004)

研究了围长至少为5的平面图的injective列表染色问题.通过分析极小反例的结构性质并利用权转移方法,证明了围长至少为5且最大度至少为12的平面图G的injective列表色数不超过Δ(G)+4.此结果进一步拓展了平面图关于injective色数的Lužar 猜想成立的充分条件.

平面图;围长;injective列表染色;面

0 引 言

图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染色问题展开了一系列的研究.定理1给出了在最大平均度的条件限制下的结果.

定理1 对于一个图 G.

另外,利用图的围长和最大度作为限制条件,有以下结果:

定理2 设图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的证明

对于一个i-点v(3≤i≤5),若v至多与2个3+-点相邻,则称v为坏i-点.

性质1

1)δ(G)≥2;

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

3)G中无相邻的2-点;

4)坏5-点不与坏i-点(i=3,4)相邻;

5)52-点v至多与1个坏3-点或1个坏4-点相邻,且v不同时与坏3-点和坏4-点相邻.

3)若u,v是2个相邻的2-点,则有SG(u)≤Δ和SG(v)≤Δ,这与性质1的2)矛盾.

4)假设坏5-点相邻坏4-点,如图1(a)所示.v是坏5-点,v4是坏4-点.根据G的极小性知,G-vv4有一个injectiveL-染色,再抹去v,v4,v42,v43,v1,v2,v3的颜色,此时它们的可用色分别至少为1,2,4,4,4,4,4.显然,可以将它们依次染好(注:若其中有2个顶点有公共邻点,则这2个顶点的可用色各增加1,下同),这样便得到了G的一个injectiveL-染色(如果v4是坏3-点,那么在改染的时候,它将会有更多的可用色).矛盾.

5)只需证明52-点不与2个坏4-点相邻,如图1(b)所示.v是52-点,v3,v4是坏4-点.根据G的极小性知,G-vv4有一个injectiveL-染色.再抹去v,v3,v4,v32,v33,v42,v43,v1,v2的颜色,它们的可用色分别至少为1,2,2,4,4,4,4,4,4.显然,可以将它们依次染好,这样便得到了G的一个injectiveL-染色.矛盾.

图1 性质1中的4)和5)的2个构型

对任意x∈V∪F，构造一个权函数μ(x)，其中当v∈V时，μ(v)=-5，当f∈F时，μ(f)=d(f)-5，则有=-10．下面根据G的结构性质，在保持总权和不变的情况下，对G中的点和面的权按一定规则进行转移，得到一个新的权函数μ'(x)．下面将证明:对任意x∈V∪F，都有μ'(x)≥0．从而得出如下矛盾:

该矛盾说明G不存在,从而定理3是成立的.

定义如下的权转移规则:

R0:3+-点给相邻的2-点转权1.

R1:设v是一个3-点,uv∈E(G).

R2:设v是一个4-点,uv∈E(G).

下面将检验μ′(v)≥0,∀v∈V(G).

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

3)d(v)=4,μ(v)=1.根据性质1的2)知,n3+(v)≥2.

接下来检验μ′(f)≥0,∀f∈F(G).

这样就检验了对任意x∈V∪F,都有μ′(x)≥0,从而得到如下矛盾的式子:

定理 3 证毕.

2 结 语

本文讨论了围长至少为5的平面图的injective列表染色问题,并证明了围长至少为5且最大度至少为12的平面图G的injective列表色数不超过Δ(G)+4.对此,笔者认为,若对平面图G的最大度作进一步的限制(如 Δ(G)≥10),对G的结构性质再作更加细致的刻画,会有同样的结果;同时,在同样的最大度条件限制下,估计会有injective列表色数不超过Δ(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]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.

(责任编辑 陶立方)

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

国家自然科学基金资助项目(11271334)

卜月华(1960-),男，浙江东阳人，教授，博导.研究方向：组合数学与图论.

O157.5

A

1001-5051(2016)01-006-07