论文部分内容阅读
设G是简单图,用颜色1,2,3…对G的边着色。如果每一顶点所关联的边上着的颜色构成一个连续的整数集合,那么就称这个边着色是连续的。图的连续边着色在日程安排理论上有重要应用,它先由Kubale在文献[9]中引入介绍并且被文献[4,6,7,9]的作者研究。图G的亏度def(G)是最小数目的悬挂边,他们粘在G上使它可连续边着色。
广义θ-图,简记为θm,是一个包含m(2≤m<∞)条内部不交的(u,v)-路的图。设P1,P2,…,Pm是这m条(u,v)-路,其中偶长路的个数定义为◇(θm),奇长路的个数定义为o(θm)。设l(Pi)为Pi的长度,lmax(θm)=maxl(Pi)。Fn*=K1+nK2是包含n个有公共顶点w的三角形的图。
设G为0-亏度图。着色c的支撑s(G,c)是指在c这个连续边着色中所使用的颜色数目。所有连续边着色中所使用的颜色最小(最大)数目定义为s(G)(S(G))。
在本文中,我们完全刻划了θm和Fn*的连续边着色问题。还给出一类亏度为1的图。此外,我们还得到三个界S(θm),s(θm)和def(G)。以下是本文的主要结论:
1.(定理3.6)设θm是广义θ-图,则def(θm)={1如果◇(θm)是奇数并且o(θm)也是奇数;0其它。2.(定理3.10)设n≥1是一个整数,则def(Fn*)={1如果n是奇数;0如果n是偶数。3.(定理3.13)设G是偶数个顶点的I-类k-正则图,G′是G的一个剖分,就是把G的一条边换为一个2长路。则def(G′)=1。
4.(定理4.4)设θm是0-亏度的广义θ-图,则S(θm)≤lmax(θm)+Δ-1。
5.(定理4.6)设θm是0-亏度的广义θ-图,则s(θm)={m如果◇(θm)是偶数;m+1如果◇(θm)是奇数并且o(θm)是偶数。
6.(定理4.8)如果G是r-正则二类图,那么def(G)≤2m-1,这里m=minc{mini|Ei|},并且c是G任一个正常的(r+1)-边着色。