朱海洋，盛景军，侯立峰，葛生联

(徐州空军学院后勤指挥系，江苏徐州 221000)

不含4-圈的平面图的L(p,q)-标号

朱海洋，盛景军，侯立峰，葛生联

(徐州空军学院后勤指挥系，江苏徐州 221000)

令G为平面图，用Δ(G)和λp,q(G)分别表示G的最大度和L(p,q)−标号数，其中p和q是满足p≥q的两个正整数.证明了若G为Δ(G)≤5且不含4-圈的平面图，则λp,q(G) ≤ (2q−1)Δ (G)+ 8p+ 14q− 11.这一结论改进了有关文献的相关结果.

平面图；4-圈；L(p,q)-标号

所有图均为无向连通简单图.对于图G，令V(G)、E(G)、Δ(G)和δ(G)分别为图的顶点集合、边集合、最大度和最小度，如果图G能画在曲面S上使它的边仅在端点处相交，则称G可嵌入曲面S.若图G可嵌入平面，则称G是平面图.平图是平面图在平面上的一个嵌入.dG(u,v)表示顶点u,v之间的距离.图G的围长g(G)是G中最短圈的长度.图G的平方图记为G2，指的是一个图满足以下条件：V(G2) =V(G)并且uv∈E(G2)，当且仅当1≤dG(u,v) ≤ 2.图G的正常k−顶点染色是映射f:V(G) → {1,L ,k}，其中f满足对任意的相邻顶点u,v，都有f(u) ≠f(v)，最小的整数k称为图G的色数，记为χ(G)，由 Brooks定理，对于任意图G，χ(G2) ≤Δ2(G)+ 1，这个上界是紧的，Petersen图和5-圈就是两个最简单的例子.其它未定义的符号见文献[1].

定义1 设p和q是满足p≥q的两个正整数.图G的k−L(p,q)−标号是一个映射ϕ:V(G) → {0,1, L,k} ，其中ϕ满足对任意的u,v∈V(G)，若dG(u,v) = 1，则p；若dG(u,v)= 2，则 |ϕ(u)−ϕ(v)|≥q.图G的L(p,q)−标号数是使G存在k−L(p,q)−标号的最小的整数k，记为λp,q(G).图G的L(1,1)−标号等价于图G2的正常顶点染色，且λ(G)=χ(G2) −1.

1,1

Wegner[2]首先研究了平面图的平方图的色数，证明了若G为 Δ (G) = 3的平面图，则χ(G2) ≤ 8，并且提出以下著名猜想：

猜想1 设G为平面图，若 4 ≤Δ (G)≤7，则χ(G2) ≤Δ (G)+5；若 Δ (G)≥8，则

1 引理及其证明

证明：假设引理1不正确，设G为 Δ (G)≤ 5且不含4-圈的平图，为不含构型（A1）–（A10）的一个反例.由于G无4-圈，所以……