论文部分内容阅读
设G=(V,E)是一个图,k,d是两正整数且满足k≥2d(k≥d如果最大度△≤1),那么图G的(k,d)-边着色是一个映射c:E(G)→{0,1,…,k-1}使得对任意相邻的边ei,ej,有 d≤|c(ei)-c(ej)|≤k-d对于图G的所有(k,d)-边着色,它的圆边色数定义为分数k/d的下确界,即 xc(G)=inf{k/d:G是可(k,d)-边着色的}对图G的圆边色数xc(G)的研究是对它的边色数x(G)的加细,在过去的几十年都十分活跃,得到了很多好的结果。
在本文中,我们主要证明了某些类图的性质并且确定了它们圆边色数的精确值。概括如下：
(1)确定了几种阶数较小的临界图的圆边色数的精确值；
(2)若K2,2和K3,3是分别细分K2,2和K3,3的一边所得的图,则 xc(K2,2)=5/2,xc(K3,3)=7/2。
(3)如果G*是一个链图(Fig.10(e)),则xc(G*)=3。
(4)图G1,G2的紧积为G1□G2.对于任意两个正整数m,n我们证明了: C2m+1口C2n是第一类的,即xc(C2m+1□C2n)=4; C2m+1□C2n+1为第二类的,且4+2/2mn+m+n≤xc(C2m+1□C2n+1)≤5.