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

项目名称： 关于图染色及相关问题研究

项目编号： No.10971198

项目类型： 面上项目

立项/批准年度： 2010

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

项目作者： 卜月华

作者单位： 浙江师范大学

项目金额： 29万元

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

中文关键词： 平面图；染色；均匀列表染色；符号控制数；容错嵌入

英文摘要：

英文关键词： planar graph；coloring；equitable list coloring；signed domination number；fault-tolerant embedding