图的（t,k,d）-树染色问题的研究

一个图的（t,k,d）-树染色是指用t种颜色去染图的边使得染同一种颜色的边导出子图是一棵森林T, 并且T的每个连通分支的最大度不超过k和直径不超过d. 使得图G存在（t,k,d）-树染色最小的整数t称为图G的(k,d)-荫度. 此概念是正常边色数、线性荫度、线性k-荫度、星荫度等概念的推广. 本课题计划得到(t,k,d)-树染色的一些一般结果，得到一些特殊图如平面图、外平面图等的(k,d)-荫度；同时继续探讨图的边色数、线性荫度和线性k-荫度等经典问题。内容涉及计算机科学、图论、规划论、矩阵论、组合拓扑等领域。问题的解决对图的染色理论和矩阵分解的发展有较大的促进作用.

在国家自然科学基金(基金号:10971121)的资助下, 项目组成员努力合作, 三年来我们共发表论文 47篇, 其中 41 篇被 SCI 刊物收录, 6 篇被中文核心刊物收录. 我们主要研究了如下内容: (1) 探讨了一些图的 (t,k,d)-树染色, 得到了一些特殊图的(k,d)-荫度; (2) 研究了图的边染色, 线性荫度, 线性 2-荫度, 均匀染色, 无圈边染色, 全染色, k-树染色, 与这些染色对应的列表染色等染色问题, 获得了一系列的结果; (3) 研究了这几类染色的色数的界及有关算法, 特别是这几类染色在1-平面图,平面图, 系列平行图等图类上的色数, 其中给出了一些图的这几种染色的确定的值, 而其它一些图给出了这几种染色的界; (4) 研究了这几类染色的分类, 以及这些染色与通常边染色分类的关系; (5) 解决了某些猜想在平面图成立..三年期间, 先后邀请了5位专家来校讲学, 并就该项目的有关问题进行了讨论. 参加国际和全国学术会议20余人次. 目前我们正在培养的博士研究生 10 名（在读）, 硕士研究生 7 名, 已获得硕士学位的硕士研究生 7 名.