论文部分内容阅读
设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)-边着色。