广义θ-链的区间边着色

陈勋¹,黄琼湘^1*,陈琳²

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

发布日期:2019-06-05

作者简介:陈勋(1993— ), 男, 硕士研究生, 研究方向为图论及其应用. E-mail:chenxjq@foxmail.com*通信作者简介:黄琼湘(1958—), 男, 博士, 教授, 博士生导师, 研究方向为代数图论. E-mail:huangqx@xju.edu.cn
基金资助:国家自然科学基金资助项目(11671344)

Interval edge-coloring of the generalized θ-chain

CHEN Xun¹, HUANG Qiong-xiang^1*, CHEN Lin²

1. College of Mathematics and System Science, Xinjiang University, Urumqi 830046, Xinjiang, China;
2. College of Medical Engineering and Technology, Xinjiang Medical University, Urumqi 830011, Xinjiang, China

Published:2019-06-05

摘要/Abstract

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


PDF全文下载地址:

http://lxbwk.njournal.sdu.edu.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3097