论文部分内容阅读
由Vizing定理可知所有的k_正则简单图可分为两类:边色数为k的第工类图和边色数为k+1的第II类图。很多著名的问题限制在第工类图上时比较容易解决,然而在第II类图上考虑时却异常困难。其中最引人关注的是第II类3一正则图,一些著名猜想的证明,如lhtte的S一流猜想、圈双覆盖猜想((CDCC)等(见1)) (2J),都是在涉及到第Ii类3一正则图时遇到了困难。另外,四色定理等价于“每一个无割边的3一正则平面图是第I类图”(见同,)。因此,我们致力于研究第II类正则图的性质和结构。
为此,我们研究第II类正则图的一个参数一色特征。令G是一个第II类k-正则图,。是G的一个正常k+1一边着色,尽_ {e E L} } c(e) _i}, i=0,1,…,k。定义。(c)=min{ } E; }}2=O,l,...,k},我们称。(G)=min }o(c)}是G的色特征,其中c(c)是由G的所有正常k+1一边着色组成cEC(G)’的集合。对于有重边的边色数为k+1的k一正则图c,我们以完全相同的方式定义它的色特征。从直观上看,二(G)是由G得到一个边色数为k_的图,所需要删除的最小边数。Vizing定理按边色数将简单图分为两类:边色数为△第I类图和边色数为△+1的第II类图。色特征的概念把第II类正则图做了细分,使得我们按照这种分类方式逐类解决那些著名的猜想成为可能。因此,本文研究第II类正则图,特别是3一正则图的色特征和它的性质,以及由色特征确定的图的结构性质。