王艺桥, 舒巧君

(1.北京中医药大学 管理学院,北京 100029;2.杭州电子科技大学 理学院,浙江 杭州 310018)

本文仅考虑有限简单图.给定一个图G,用V(G),E(G)和Δ(G)分别表示它的顶点集、边集和最大度.图G的正常k-边染色是指映射c：E(G)→{1,2,…,k},使得相邻的边染不同的颜色;若G有一个k-边染色,则称图G是k-边可染的;边色数χ′(G)是指使得图G是k-边可染的最小整数k;无圈k-边染色是指图G的一个正常的k-边染色,使得任一个圈上至少有3种不同的颜色;无圈边色数a′(G)是指使得图G是无圈k-边染色的最小整数k.

若无混淆,下文均将Δ(G)简记为Δ.根据Vizing定理[1],Δ≤χ′(G)≤Δ+1.显然,Δ≤χ′(G)≤a′(G).

猜想1对任意图G,a′(G)≤Δ+2.

猜想1至今尚未得到证实,但对一些特殊图已被证明猜想1成立.Alon等[6]证明了确定一个图G的无圈边色数是一个NP-问题.关于完全二部图、最大度为3的图及最大度为4的图的无圈边色数的研究可参见文献[7-9].对于平面图G,Basavaraju等[10]证明了a′(G)≤Δ+12;后来文献[11]将上界Δ+12降到Δ+7.

若图G存在一个平面嵌入,使得它的所有顶点在一个面的边界上出现,则称G为外平面图.令H2n表示在2n-圈x1x2…x2nx1上添加n-1条弦x2x2n,x3x2n-1,…,xnxn+2后所得的图,Q表示在7-圈y1y2…y7y1上加弦y2y7,y2y6,y3y5,y3y6后所得到的图,如图1所示.

图1 图H2n,Q,S1和S2

设G是一个外平面图.2007年,Muthu等[12]证明了a′(G)≤Δ+1.文献[13]改进了这个结果,即证明了：当Δ≥5 时,a′(G)=Δ;当Δ=3且G是2-连通时,a′(G)=4当且仅当G含有与H2n同构的子图.此外,文献[13]还断言:若Δ=4,则4≤a′(G)≤5,且a′(G)=5当且仅当G含有与Q同构的子图.然而,这个结论是不正确的.事实上,王维凡等(在一篇未发表的论文中)构造出图S1和S2有a′(S1)=a′(S2)=5,但S1和S2均不含与Q同构的子图,如图1所示.

本文旨在给出一个最大度为4的外平面图的……