李艳怡，陈莉莉

(华侨大学 数学科学学院，福建 泉州 362021)

1 预备知识

平面图是一类重要的特殊图，关于平面图的单射点染色已经得到较多结果.文献[4-6]研究了平面图的单射点色数与最大度、围长之间的关系及围长至少为7，5时平面图的单射点色数；Dong等[7]在围长为6的条件下研究平面图的单射点色数；朱海洋等[8]考虑最大度Δ(G)≤6且不含4，5，6，7-圈的平面图的单射点色数的上界.除此之外，学者们还考虑了平面图的单射可选性，即对图G的每个点v分配一个列表L(v)，要求单射染色f需满足f(v)∈L(v)，这样的染色称为列表单射染色.文献[9-12]在围长限制下研究平面图的列表单射色数的界；Brimkov 等[13]考虑了围长为6的次立方平面图的单射可选性；卜月华等[14]考虑了5--圈和 5--圈不交的平面图的列表单射染色.对于单射边染色，Bu等[15]在限制最大度及最大平均度条件下，给出了稀疏图单射边色数的上界；卜月华等[16]研究了围长至少为6且6-圈与7--圈不相交的平面图G的单射边色数.

讨论简单次立方平面图的单射边色数.设G=(V，E)是简单平面图，Δ=Δ(G)为G的最大度，如果Δ(G)≤3，则称G是次立方图.围长g表示G中最短圈的长度.得到以下2个定理.

使用权转移的方法进行定理的证明.权转移的主要思想是对图G的点和面进行赋权，使得初始权值之和为负数.研究图内部的结构性质并且给定权转移规则，进行点点之间，面面之间及点面之间的权值转移，最终得到新的权值之和为非负数.由于权转移过程是在图内部进行的，所以总权值应当不会变化，这就导出了矛盾.

在下面的证明中，对于图G的一个染色f，任意e∈E(G)，用F(e)表示在染色过程中边e不能使用的颜色集合.

2 定理1的证明

引理1图G不存在1度点.

证明：假设图G存在1度点u，v是它唯一的邻点.令G′=G-u，由G的极小性，存在G′的用6种颜色的单射边染色f′.因为|F(uv)|≤4，所以令f(uv)∈CF(uv)，而对e∈E(G){uv}，有f(e)=f′(e).这样就得到G的用6种颜色的单射边染色f，与假设矛盾.

引理2图G中2度点只能和3度点相邻.

证明：假设u，v是G中2个相邻的2度点，w是v的另一个邻点.令G′=G-v，由G的极小性，存在G′的用6种颜色的单射边染色f′.因为|F(uv)|≤4，|F(vw)|≤5，所以可以先对边vw染色，再对边uv染色，此外，对于e∈E(G){uv，vw}，有f(e)=f′(e).这样就得到G的用6种颜色的单射边染色f，与假设矛盾.

引理3G中3度点最多和1个2度点相邻.

证明：假设u是G中1个3度点，u与2个2度点v和w相邻，u的另一个邻点为u1，w的另一个邻点为w1.令G′=G-u，由G的极小性，存在G′的用6种颜色的单射边染色f′.删去边ww1上的颜色，此时，|F(uv)|≤4，|F(uw)|≤5，|F(uu1)|≤5，|F(ww1)|≤4，所以先对边uu1进行染色，再染边ww1，最后分别对边uv，uw进行染色.此外，对于e∈E(G){uv，uw，uu1，ww1}，有f(e)=f′(e).这样就得到G的用6种颜色的单射边染色f，与假设矛盾.

根据平面图的欧拉公式

V-E+F=2，

以及握手定理

可以得到

分别对图G的顶点和面进行初始赋权，∀v∈V(G)，令ω(v)=2d(v)-6，∀f∈F(G)，则令ω(f)=d(f)-6，那么可以得到初始总权值为

给定权转移规则R：每个面给该面上的每个2度点权值1.

如果v是2度点，则初始权值ω(v)=-2.因为2度点存在2个面上，且从每一个面得到1的权值，所以得到新的权值ω′(v)=-2+1+1=0.

如果v是3度点，则初始权值ω(v)=0.由于3度点没有进行权转移，所以新权值ω′(v)=0.

由于g≥8，即d(f)≥8，所以ω′(f)≥0恒成立.

由于权转移是在图内部进行，所以总权值不会变化，也就是

出现矛盾，所以极小反例G不存在，定理1得证.

3 定理2的证明

引理5图G不存在1度点.

证明：假设G中存在1度点u，v是它唯一的邻点.令G′=G-u，由G的极小性，存在G′的用7种颜色的单射边染色f′.因为|F(uv)|≤4，所以令f(uv)∈CF(uv)，而对e∈E(G){uv}，f(e)=f′(e).这样得到G的用7种颜色的单射边染色f，与假设矛盾.

引理6图G不存在2度点.

证明：假设u是G中的2度点，w和v是它的两个邻点，令G′=G-u，由G的极小性，存在G′的用7种颜色的单射边染色f′.因为|F(uv)|≤6，|F(uw)|≤6，且边uw和uv可以染相同的颜色，因此，可以得到G的用7种颜色的单射边染色f，与假设矛盾.

给定点的初始权值为∀v∈V(G)，ω(v)=2d(v)-6，面的初始权值为∀f∈F(G)，ω(f)=d(f)-6，根据欧拉公式，初始总权值为

根据以上所得性质，G中只存在3度点，因此，所有点的总权值为

对于面，由于g≥6，即d(f)≥6，所以得到所有面的总权值为

最终可以得到

出现矛盾，也就是极小反例G不存在，定理2得证.

4 结束语

通过极小反例及权转移的方法，研究次立方平面图的结构性质，最终得到其在限制围长条件下的单射边色数的上界.