-
广义θ-链的区间边着色
- 陈勋,黄琼湘,陈琳
-
2019, 54(6):
59-70.
doi:10.6040/j.issn.1671-9352.0.2017.577
-
摘要
(
1284 )
PDF (899KB)
(
495
)
收藏
-
参考文献 |
相关文章 |
多维度评价
如果图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的亏度。