姚顺禹,马登举

(南通大学理学院,江苏南通 226019)

1 引言

在图G=(V(G),E(G))中,V(G),E(G)分别表示图G的顶点集合,边集合.图G的一个k-边正常染色是指一个映射f:E(G)→ {1,2,···,k},使得对于任何两个相邻的边e1,e2,均有f(e1)f(e2),图G的k-边正常染色又简称为k-边染色.设G是一个图,e1=u1v1,e2=u2v2是图G中的两条边.若e1与e2相邻,则称e1与e2的距离为0,若e1与e2不相邻,从e1的一个端点到e2的一个端点的路称为e1到e2的一条路.e1与e2的距离是指在e1到e2的所有路中一条最短路所含的边数.图G的k-强边染色是一种k-正常染色,使得任意相邻于同一条边的两条边不得染相同的颜色.换句话说,图G的强边染色是一种边染色,使得任意两条距离不大于1的边被染不同颜色.图G的强边色数(G)是最小的k,使得G有一个k-强边染色.

1985年,Erdös和Nešetil[1]给出了关于强边染色的概念,并提出了如下猜想:对于最大度为ΔG的图G,Molloy和Reed[2]证明了当ΔG足够大时,(G)≤这里 ∈约为.而Bruhn和Joos[3]进一步证明了Andersen[4]证明了一个3-正则图G的强边色数

麦比乌斯梯子C(2n,n)是这样一个图,它的顶点集为V={vi|i=1,2,···,2n},边集为E={vivi+1,vivi+n|i=1,2,···2n},这里的加法在取模2n的情况下进行.它是一个3-正则图,可以嵌入在射影平面上,当n=3时,C(2n,n)就是K3,3.本文研究了C(2n,n)的强边色数,得到如下结果:当n=3时,当当n=5,8时当n≥3且n≡2(mod 4)时,当n≥7且n≡0,1或3(mod 4)时,

2 主要结论

在本节的开始,先给出C(2n,n)的强边色数的一个下界.

当n=2时,C(2n,n)即为K4,因为K4中任意两条边之间的距离都小于2,且K4含有6条边,所以χ′s(C(4,2))=6.接下来,考虑n≥3的情形.

引理2.1当n≥3时,χ′s(C(2n,n))≥6.

证当n≥3时,C(2n,n)有一个导出子图同构于如图1所示的图H.不难发现图H中任何两条边之间的距离都不大于1.因图H 含有6条边,故(H)≥ 6,从而

图1:图……