图的染色问题及其在网络中的应用

Graph coloring is a classic field of research, and now it is still very active with appearances of many new problems. Graph coloring enjoys many practical applications as well as theoretical challenges. Complex network is an emerging and popular field of research, and graph theory is one of its basic theory needed in mathematics. In this project we will research some classic problems of graph colorings, firstly present and research the acyclic vertex arboricity and acyclic arboricity of graphs, explore the applications of graph colorings in networks. Our aim is to determine the total chromatic number, list edge (or total) chromatic number, linear arboricity and acyclic (vertex) arboricity of some large classes of graphs, solve or partly solve some related famous conjectures, design good algorithms and use them to analyze the structure of complex networks. One part of this project is the research of some classic problems of graph colorings, one part is the research of some new problems presented by us, and the remaining part is the research of the applications in complex networks. It is related to the research field of graph theory, matrix theory, programming theory, probability theory, combinational topology, complex network, etc. The solutions of the problems in this project will promote the development of graph coloring and network optimization.

图的染色理论是图论中一个经典且新问题不断涌现的分支，它有着深刻而丰富的理论成果和广泛的应用背景。复杂网络是一个新兴的热门研究领域，而图论是其研究所依赖的主要数学基础理论之一。本项目将研究图的染色理论中的几个经典问题，首次提出并研究图的无圈点荫度和无圈荫度，探索图的染色理论与方法在网络研究中的应用。我们力求确定一些大的图类的全色数、列表边（或全）色数、线性荫度、无圈（点）荫度等，解决或部分解决相关的几个著名猜想，设计出好的算法并应用于复杂网络的结构分析中。本项目所研究的内容一部分是经典的染色问题，一部分是我们提出的新问题，还有一部分是上述理论在复杂网络中的应用，内容涉及图论、矩阵论、规划论、概率论、组合拓朴、复杂网络等领域，问题的解决对图的染色理论、网络优化等有较大的促进作用。

在本项目三年的执行期内，项目组成员按照项目书中的计划，主要围绕几个著名的猜想研究了图的全染色、列表染色、线性荫度等问题，刻画了图的结构性质，并利用图论的思想方法对复杂网络进行了研究。项目组成员共发表了与本项目相关的SCI论文23篇，成功申请国家级及省部级科研项目5项，取得了项目的预期研究成果，超额完成了预期的研究任务。. (1) 在全染色方面，我们主要围绕全染色猜想展开研究，证明了除了最大度Δ=6的情形以外，全染色猜想对于可嵌入到欧拉示性数为非负的曲面上的图是成立的。更进一步，对于其他一些有最大度和圈长限制的图类，我们还得到了其全染色数。(2) 在列表染色方面，我们主要围绕列表染色猜想和列表全染色猜想展开研究，得到了一些较大图类的列表边色数和列表全色数。(3) 在荫度方面，我们主要围绕线性荫度猜想展开研究。对于可嵌入到欧拉示性数为非负的曲面上的图，我们彻底解决了线性荫度猜想。另外，在一定限制条件下，我们还确定了图的线性荫度。（4）在复杂网络方面，项目组成员基于图论的理论方法对社区网络、社会网络等实际网络进行了研究。对于社区网络，我们提出了一个有效的双最短路策略去避免信号拥堵，计算机模拟的结果显示我们的算法要优于几个主要的已知方法并且用时较少。另外，我们还研究了社会网络，我们提出了一个模型强调了人的异质性对于信息传播的影响。