吴燕青

(山西师范大学数学与计算机科学学院,山西临汾 041000)

1 引言

本文主要考虑不含孤立边的有限简单图.对图G,用V(G),E(G),∆(G)和mad(G)分别表示图G的顶点集,边集,最大度和最大平均度.在G中,用NG(v)表示顶点v的邻集.度为k的顶点称为k-顶点.度至少为(至多为)k的顶点称为k+-顶点(k−-顶点).用di(v)表示与顶点v相邻的i-顶点的数目.一个图G称为半正则的,如果它的每一条边至少和一个最大度顶点相关联.否则,称为非半正则的.一个图G的正常边着色是一个映射φ:E(G)→{1,···,k},使得每一对相邻边e1和e2,有φ(e1)(e2).用cφ(v)表示在着色φ下与v相关联的边所着的颜色组成的集合.一个图G的正常边着色φ称为邻点可区别边着色,如果G的任何相邻顶点u和v,满足cφ(u)(v).G的邻点可区别边色数是使得G有一个k-邻点可区别边着色的最少颜色数k.

在2002年,文献[1]首先讨论了邻点可区别边着色问题,并提出了以下猜想.

猜想设图G为顶点数至少为3的连通图且5,则.对于一般图G,文献[2]给出了若∆(G)>1020,则.文献[3]给出了.文献[4]给出了.文献[5]给出了若∆(G)≤3,则.文献[6]给出了若∆(G)≤5且,则.文献[7]给出了若∆(G)≤4,则,和若∆(G)≤5,则.本文证明了若G是一个最大度为6的非半正则图,则.

引理1.1[7]假设G是一个∆(G)≥2的半正则图.若∆(G)≡0(mod 3),则.

2 主要结果

定理2.1设G是一个最大度为6的非半正则图,则.

证假设G是含边数最少的连通的极小反例.由于G是非半正则的,所以存在uv∈E(G),使得dG(u)≤5且dG(v)≤5.不妨设dH(u)≤dH(v).设H=G−uv,由G的极小性可知,H有一个12-邻点可区别边着色φ,它用的颜色集C={1,2,···,12}.为了叙述起来方便,称在φ下边e对颜色α是允许的,若在φ下用颜色α给边e重新着色可得H……