王维凡, 杨灿权

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

0 引 言

本文中所考虑的图都是有限简单图.设V(G),E(G),Δ(G)分别表示图G的顶点集、边集和最大度,将Δ(G)简记为Δ.图的染色理论是图论研究的一个重要内容.图的染色就是对顶点、边等图的元素进行分类,使得它们满足某些特定性质.不同的性质和要求就导出不同的染色方式.图论染色理论中最经典的染色就是正常点染色和正常边染色.本文主要研究图的边染色.

图G的一个正常k-边染色是指一个映射φ:E(G)→{1,2,…,k},使得相邻的边染不同的颜色.图G的边色数χ′(G)定义为最小的正整数k,使得G有一个正常k-边染色.

任意一个最大度为Δ的图G,由于相邻的边需要染不同的颜色,自然可以得到χ′(G)≥Δ.1964年,Vizing[1]证明了下面的一个图论中最重要的结果之一：

定理1[1]对于任意简单图G,Δ≤χ′(G)≤Δ+1.

若χ′(G)=Δ,则称G是第一类的,否则称G是第二类的.对一般图而言,尽管只有2个选择,但要确定是否属于第一类是NP-完全的[2],于是,学者们开始寻找使图G是第一类或第二类图的充分条件.

给定一个最大度为Δ的图G,设GΔ表示由G的所有最大度点导出的子图.基于这个特殊的子图,Fournier[3]给出了下面十分有意义的结果：

定理2[3]对简单图G,若GΔ是一个森林,则G是第一类的.

对于平面图G,Vizing[4]证明了:当Δ≥8时,G是第一类图;而当2≤Δ≤5时,存在第二类的简单平面图G.文献[4]中提出猜想:当6≤Δ≤7时,简单平面图G是第一类的.Sanders等[5]和张利民[6]分别独立证明了当Δ=7时Vizing猜想成立.但当Δ=6时,该猜想至今悬而未决.很多学者给出了部分结果……