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

项目名称： 图的（t,k,d）-树染色问题的研究

项目编号： No.10971121

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 数理科学和化学

项目作者： 吴建良

作者单位： 山东大学

项目金额： 24万元

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

中文关键词： 图；树染色；荫度；边色数；

英文摘要：

英文关键词： graph；tree coloring；arboricity；edge coloring；