论文部分内容阅读
图G的区间全着色是G的一个使用了颜色1,2,…,t的全着色,并且每种颜色都使用过,关联于顶点v的所有边连同顶点v使用dG(v)+1种连续的颜色,dG(v)是顶点v在G中的度.如果对某个正整数t,图G存在一个t-区间全着色,则称图G是可t-区间全着色的.令:此处公式省略表示可t-区间全着色的图集,对任意的G∈ζ,使得图G存在一个t-区间全着色的t的最小值和最大值分别记为Wt(G)和Wt(G)。 本文研究几类图的区间全着色,首先证明了广义θ-图θm是可区间全着色的,并且:此处公式省略其中l表示θm中最长的一条(u,v)-路的长度,ll表示θm中除上述(u,v)-路外最长的一条(u,v)-路的长度.然后证明了路Pn的广义Mycielski图um(Pn)是可区间全着色的,对任意的m≥1,n≥2,um(Pn) G∈ζ且:此处公式省略。最后得出3-正则哈林图H是区间全着色的。