山东大学学报(理学版)

作者：陈勋,黄琼湘,陈琳

单位：1. 新疆大学数学与系统科学学院, 新疆 乌鲁木齐 830046;2. 新疆医科大学医学工程技术学院, 新疆 乌鲁木齐 830011

关键词：区间边着色,亏度,广义θ-图,广义θ-链,

基金：国家自然科学基金资助项目(11671344)

如果图G的一个边着色用了1,2,…,t中的所有颜色,并且关联于G的同一个顶点的边上的颜色各不相同,且这些颜色构成了一个连续的整数区间,则称这个边着色是G的区间t-着色。如果对某个正整数t,G有一个区间t-着色,则称G是可区间着色的。所有可区间着色的图构成的集合记作N。图G的亏度def(G)是粘在G的顶点上使它可区间着色的悬挂边的最小数目,显然,G∈N当且仅当def(G)=0。广义θ-链是把路P=［v0,v1,…,vk］(k≥1)的每一条边vi-1vi(i=1,2,…,k),用mi≥2条两两内部不交的(vi-1,vi)-路替换掉而得到的简单图,记作θm1,m2,…,mk。把广义θ-图亏度的结论进行推广,确定了θm1,m2,…,mk的亏度。

来源：2019年第6期

《山东大学学报(理学版)》期刊编辑部

查看山东大学学报(理学版)杂志2019年第6期