图的连通染色

Colored notion of connectivity in graphs aims to study the chromatic numbers of graphs whose vertices are pairwisely connected by some kinds of colored paths, including rainbow connections numbers, proper connection numbers, conflict-free connection numbers, monochromatic connection numbers, etc., which is an extension for the graph coloring theory, and an interdiscipline of the two main branches colorings and connectivity of graphs. This concept has important application backgrounds in safety theory of information transmissions, and the optimal assignments of channels. Recently, study on this subject has been developed rapidly. Plenary or invited speakers of the International Congress of Mathematicians, such as Frieze, Krivelevich, Sudakov etc., as well as many famous graph theorists in USA, Israel, Germany, France, Japan, etc., all have taken part in this research field, and they have got a lot of very excellent results. Our work on this subject has also attracted extensive attention of research peers. Invited by the world famous publisher Springer, we published 3 books along with this subject. However, many hard and interesting unsolved problems and conjectures in this field still exist. This is the main research subject of our this project. Meanwhile, investigation on the relationships among these chromatic parameters, as well as with other graph parameters is also the purpose of our this project. By systematical, deep and long time study, we expect to produce a new branch in the coloring theory of graphs.

图的连通染色研究图的顶点间可用某种有色路连通起来的色数问题，包括彩虹连通数、正常连通数、无冲突连通数、单色连通数等，它是对图染色理论的扩充，是图的染色与连通性两个重要分支的交叉，它在网络信息传送的安全性和通讯网络的最佳信道安排方面有重要的应用背景。近年来这方面研究得到了迅速发展，国际数学家大会报告人Frieze、Krivelevich、Sudakov等人，以及美国、以色列、德国、法国等许多国家都有从事这方面研究的著名图论专家，做出了非常优秀的研究成果。我们的研究也得到了国际同行的广泛关注，应世界著名出版公司Springer之邀出版有关专著3部。但是对它的研究仍然存在着许多困难而饶有兴趣的未解决问题和猜想，这是本项目所关注的主要目标。另外，研究这些色参数之间的关系，以及与图的其他参数之间的关系也是本课题的目标所在。通过系统深入和长期的研究，以期在图的染色理论中发展出一个全新的研究分支。

四年来，本项目在国家自然科学基金的资助下，在项目组成员的一致努力下，取得了丰富的研究成果，完成了项目预期的各项主要目标。发表论文56篇，其中52篇为SCI检索期刊，在高教出版译著1部；培养毕业博士14人、博士后出站1人、硕士8人。. 本项目研究了图的彩虹连通数与彩虹不连通数、单色连通数与单色不连通数、正常连通数与正常不连通数、以及无冲突连通数等这些连通染色数。在算法复杂性方面，虽然早已证明对于图的彩虹连通数它是NP-困难的，但对于其他三类连通染色数一直没有解决，我们证明了图的单色连通数、正常连通数和无冲突连通数的算法问题也都是NP-hard的，这解决了该领域里长期困扰人们的问题，进而解决了其它每个连通和不连通染色数的算法复杂性问题，并对一些图类给出了多项式时间算法；对每个连通和不连通染色数得到了最佳上下界以及极图刻画；解决了关于每个连通和不连通染色数的Erdos-Gallai型和Nordhaus-Gaddum型的极值问题，分别对应着参数型的Turan极值问题和参数型的Ramsey极值问题；对于Erdos-Renyi型的随机图模型G(n,p)，确定了每一个连通和不连通染色数的值达到给定值时，其边概率p的门槛值；证明了它们与著名的四色问题之间的等价关系；得到了它们之间以及与其他参数之间的一些换算公式。这些结果发表在本领域重要国际学术期刊Discrete Math.、Theoret. Computer Science、J. Comb. Optim.、Discrete Appl. Math.、Graphs & Comb.等杂志上。此外, 还在图的整数流、边染色图的子图、图的秩、谱、能量、拓扑指标等其他方面做出了重要的研究结果，解决了国际同行提出的若干困难问题，建立了研究图的度函数加权拓扑指数和邻接矩阵的谱等极值问题的统一框架，这些结果发表在本领域重要国际学术期刊Siam J. Discrete Math.、J. Graph Theory、Theoret. Computer Science、Discrete Math.、Linear Algebra Appl.、Discrete Appl. Math.等杂志上。