几类图染色问题的研究

图的染色问题一直是图论研究的热门问题之一, 其研究对图论的发展有着重要的理论意义, 并且在Hessin矩阵的计算、数据传输、大规模集成电路的设计、网络优化等方面有着重要的应用价值. 本项目主要研究图染色理论中几个热点问题, 其中包含全染色、列表染色、无圈染色、f-染色等. 力求解决上述染色中的几个基本问题, 并且确定某些特殊图的全色数、列表色数、无圈边色数、f-色数等, 解决图染色问题中几个著名的猜想, 利用无圈染色计算Hessian矩阵, 设计上述染色的多项式时间算法, 将其应用在网络设计和大规模集成电路优化上. 本项目所研究的问题是图的染色理论中经典的问题, 内容涉及图论、规划论、矩阵论、概率论、组合拓扑等领域. 问题的解决对图的染色理论、矩阵分解和网络优化的发展有较大的促进作用.

图的染色问题一直是图论研究的热门问题之一, 其研究对图论的发展有着重要的理论意义, 并且在Hessin矩阵的计算、数据传输、大规模集成电路的设计、网络优化等方面有着重要的应用价值. 本项目主要研究了图的无圈染色、全染色、线性荫度等, 给出了平面图无圈边色数新的上界, 研究了围长较大的平面图的无圈边染色, 给出了其无圈边色数, 给出了含有三角形的平面图无圈边色数的上界, 验证了特殊情形下的无圈边染色猜想, 用概率方法研究了围长较大的图的无圈边染色. 在线性荫度方面取得重要进展, 得到了最大度至少是9平面图的线性荫度. 在全染色面, 主要考虑不含短圈的平面图的全染色, 给出其全色数, 改进了原有结果.