论文部分内容阅读
设G是简单图,用颜色1; 2, 3,…对G的边正常着色,如果在每一顶点表现的颜色构成一个连续的整数集合,那么就称这个着色是连续的.图的连续边着色对应于没有等待时间的日程安排问题.不是所有的图都有连续边着色.图G的亏度de f (G)是粘在G上使得它可连续着色的悬挂边的最小数目侧.
通常要确定一个图是否有连续边着色是比较困难的,而且己刻划的图只有很少的一部分.事实上,Sevastjanov在[s]中己经证明了即使是对一个给定的二部图,要确定它是否有连续边着色也是NP完全的.
仙人掌是一个每个块是圈或Kz的图.从定义可知一个仙人掌的任意两个不同的圈至多有一个公共点.用of必表示图‘中包含的奇圈个数,尺表示由n个只有一个公共顶点的三角形构成的图.如果一个图G有导出子图G1和Gz使得G二Gl、 Gz并且G1nGz=Ifi,则称G是G,和G:在顶点?的粘,记作G二Gi vv Gz,其中?E Y(Gl n Gz).
在本文中,我们研究仙人掌的连续边着色问题.我们确定了奇.数不超过2的仙人掌的亏度,给出了一个无割边且奇圈数是数的仙人掌可连续着色的充分条件,并且证明了无割边且奇圈数是奇数的仙人掌是不能连续着色的.此外我们还给出了两类亏度为1的仙人掌。