严晓燕， 卜月华

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

0 引 言

本文仅考虑无向简单图.给定一个图G,用V(G),E(G),Δ(G),δ(G),g(G)和dG(u,v)分别表示图G的顶点集、边集、最大度、最小度、围长及G中顶点u,v间的距离.对x∈V(G),用dG(x)表示G中x的度,简记为d(x).若d(v)=k(或d(v)≥k,或d(v)≤k),则称v为一个k-点(或k+-点,或k--点).对平面图G,用F(G)表示G的面的集合,并且可以类似地定义k-面,k--面,k+-面.

图G的k-2-距离染色是指映射c:V(G)→{1,2,…,k},使得对G中满足0

关于平面图的2-距离染色,文献[1]提出了如下猜想:

对于2-距离列表染色,文献[10]提出了如下猜想:

定理1 若平面图G满足Δ(G)≤5,则下列结论成立:

1 符号说明

设v∈V(G),用NG(v)表示G中v的邻点集合,nk(v)表示与v相邻的k-点的个数.称与2-点相邻的3-点为星.对于图G中的顶点v,设v1,v2,…,vd(v)为v的邻点,不妨设d(v1)≤d(v2)≤…≤d(vd(v)).用(d(v1),d(v2),…,d(vd(v)))表示v.为方便,也用邻点的名字来代替其度数,例如,4-点(2,2,x,y)表示这个4-点的邻点为2个2-点及x和y,且d(x)≤d(y).对于图G的一个顶点染色c,v∈V(G),令C(v)={c(u) | u∈V(G),0

2 定理1的证明

因为定理1的3个部分是完全独立的,所以将分3个引理来证明.

性质1 δ(G)≥2.

性质2 G不含相邻2-点.

证明 假设G含有相邻2-点.不妨设uv∈E(G)且d(u)=d(v)=2.由G的极小性知,G-uv有一个L-2-距离染色.抹去u,v的颜色,则u,v的禁用色个数均至多为6,故u,v可以被重新染好.因此,G是L-2-距离可染的.得到矛盾.性质2证毕.

性质3 若3-点v为(2,x,y)-星,则x,y均为5-点.

证明 假设d(x)+d(y)≤9,且设与v相邻的2-点为u.由G的极小性知,G-uv有一个L-2-距离染色.现将u,v的颜色抹去,则v的禁用色至多有10个,故可将v染好.此时,u的禁用色至多有8个,也可以将u重新染好,从而G是L-2-距离可染的.矛盾.因此,d(x)+d(y)≥10,但因Δ(G)≤5,故x,y均为5-点.性质3证毕.

性质4 若4-点v为(2,2,x,y)-点,则d(x)+d(y)≥9.

证明 假设u,w是与v相邻的2个2-点,且设……