关于图染色及相关问题研究

图的染色及其在相关学科中的应用一直是图论研究的热点，是推动组合数学和理论计算机科学向前发展的源动力之一，属组合数学、算法设计与分析及通迅领域的交叉学科。本项目主要研究图的染色理论及图论在通迅网络中的应用。用权转移方法研究一类平面图和曲面图的结构性质，从而探讨这些图类的3-可染问题、均匀(列表)染色、各种意义下的均匀全染色点可区别染色和星染色，围绕著名的Steinbergr关于3-可染猜想和Kostochka等的均匀列表染色猜想展开重点研究，进一步扩展满足这些猜想的图类；用最大平均度、围长等参数来刻划平面图、低度图等稀疏图的星色数；用概率方法估计阶数充分大的图的均匀（全）色数和点可区别色数；考虑一些著名网络的限制容错嵌入性质并设法确定其可靠性参数（如超连通度、坚韧度等），并对容错嵌入和参数估计作算法分析。本项目拟在三年内完成学术论文20余篇。其中一半以上发表在SCI杂志上。

本项目主要研究图的染色理论、连通性问题、图的控制数及其图的带宽、割宽等问题。用一次或多次权转移方法研究一类平面图的结构性质，从而探讨这些图类的3-可染问题、均匀(列表)染色、星染色、BB-染色和图的标号。对于均匀（列表）染色，我们主要围绕Meyer等提出的均匀列表染色猜想展开研究，证明了外平面图、2-退化图和围长至少为6的平面图均匀列表染色猜成立,同时给出了一些不含特殊圈的平面图均匀（列表）染色数的界。对于图的BB-染色，我们主要讨论了含奇圈但不含若干特殊短圈的连通平面图关于生成树的BB-染色，同时也给出了一些特殊的图类，如Halin图、伪Halin图、完全图、轮等关于生成树和Hamilton路的BB-染色问题。对于平面图的全染色问题，研究了以最大度和不含若干特殊短圈为条件，讨论了几类平面图的全可染性问题，给出了若干平面图的列表全色数等于全色数的充分条件。对于平面图的 -标号问题，主要围绕著名的Wegner猜想展开研究，证明了对于围长至少为6的平面图，Wegner猜想成立，得到了不含4-9圈的平面图的 -标号、围长至少为6的平面图的 -标号、最大度至多为6的的平面图的 -标号等，同时给出了若干不含某些特殊短圈的平面图的 -标号的界。对于平面图的3-（列表）染色问题，首先研究了关于没有4种长度短圈的平面图的顶点3-染色和列表3-染色，在前人工作的基础上，基本完成了两个阶段性的研究成果，即没有4，i，j，k-圈(4<i<j<k≤9)的平面图是3-可染的, 和没有4，i，j，9-圈(4<i<j<9)的平面图是列表3-可染的。另外还给出了若干平面图是3-列表可染的充分条件。对于限制条件下的图的容错嵌入问题，我们考虑了一些著名图类、网络的限制容错嵌入，研究了exchanged hypercube中的圈的嵌入情况，确定了它的连通度和超连通度连通度以及折叠立方体网络的支撑连通度。对于图的符号控制数问题，我们研究了一些图类的符号全控制数，得到了一些有意义的结果。证明若干k-正则图的UPPER减控制数的下界，利用构造性方法构造出了达到该下界的图类。确定了等完全二部图、超立方体图的符号边全控制数的精确值。. 本项目所得结果改进了前人的一些工作，推进了一些著名猜想。至今完成学术论文56篇，其中被SCI收录检索的有31篇，培养硕士研究生25名，圆满完成了本课题所预定的研究任务