不含5-圈的平面图的无圈边着色

吴燕青,谢德政,赵灿鸟

(1.山西师范大学数学系,山西临汾 041000;2.重庆大学数学与统计学院,重庆 401331)

不含5-圈的平面图的无圈边着色

吴燕青1,2,谢德政2,赵灿鸟2

(1.山西师范大学数学系,山西临汾 041000;2.重庆大学数学与统计学院,重庆 401331)

图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界.

无圈边着色;无圈边色数;平面图

1 引言

本文所考虑的图都是有限简单图.文中未加定义的术语和记号看文献[1].如果图G的一个顶点的度为k(至少为k),称它为G的一个k-顶点(k+-顶点).如果一个图G的一个面的度为3,称它为三角形.一个图G的正常边着色是一个映射φ:E(G)→{1,…,k},使得对每一对相邻的边e1和e2,有φ(e1)/=φ(e2).一个正常的边着色φ被称为是无圈的,如果着色φ中不存在双色的圈.设c:E(G)→{1,…,k}是G的一个无圈边着色,且C={1,…,k}.图G的无圈边色数是G的无圈边着色中所用色数的最小者,用(G)表示.如果一个图G能用k种颜色对它进行无圈边着色,那么称这种着色为G的无圈边k-着色.

2001年,文献[2]提出了无圈边着色猜想(简称AECC):对于任意的图G,有

2 主要结论

如果d(f)=4,那么w′(f)=w(f)=0.如果d(f)≥6.根据(R1),显然w′(f)≥0.

因此,对于x∈V(G)∪F(G),有w′(x)≥0.引理1.1成立.

为了叙述方便,给出以下定义和记号.关于G的一个部分着色c,颜色α∈C对于某条边e称为是候选的,如果e的邻没有被着颜色α.我们用Rc(e)表示在着色c下由边e的候选颜色组成的集合.关于G的一个部分着色c,如果一条路上所着的颜……