图的新染色问题以及在复杂网络中的应用

Graph coloring theory is a classical and very active field in graph theory and new problems emerge in an endless stream. Complex network is a new hot subject over the past ten years, it studies basic properties and relationships of large-scale networks in nature and society. This project is studied from three aspects. Firstly, in addition to continueing to study some classic coloring problems, we focus on some new colorings of graphs, such as equitable (linear) vertex arboricity, equitable arboricity, acyclic (vertex) arboriity, acyclic (vertex) linear arboricity and so on; Secondly, combined with practical problems as well as the characteristics of complex networks, we do some research on graph coloring problems and algorithms related to complex networks. By using these results and algorithms, we may solve some related problems of complex networks. Finally, we disucuss the change rules of some coloring parameters of graphs in growing networks and natural networks, and then obtain some new characteristics of complex networks.

图的染色理论是图论领域中一个经典而且新问题层出不穷的非常活跃的分支，复杂网络是近十年来新兴的非常热门的一门学科, 它研究的是自然社会中超大规模网络的基本性质和变化规律。本项目从三个方面来展开研究：首先我们除了继续研究图的一些经典染色外，还重点研究图的一些新染色，如图的均匀（线性）点荫度、均匀荫度、反圈（点）荫度、反圈线性（点）荫度等；其次结合实际问题以及复杂网络的热点问题，研究与复杂网络有关的图的一些染色问题及相关算法，利用这些结果、算法和思路反过来解决复杂网络中的一些难的问题；最后探讨图的一些染色参数在增长网络和实际网络中的变化规律，获得复杂网络的新的特性。

本项目研究了两方面的内容：图的染色问题和复杂网络。图的染色理论是图论领域中一个经典而且新问题层出不穷的非常活跃的分支，复杂网络是近十年来新兴的非常热门的一门学科, 它研究的是自然社会中超大规模网络的基本性质和变化规律。..在复杂网络方面，我们获得了如下主要成果：（1）我们首次提出领导者社团和自组织社团的概念，并通过实际网络发现绝大部分社团是领导者社团；（2）给出一种概率方法来解释友谊悖论，并论证了用概率方法来解释的优越性；（3）建立了一类新的SICR谣言模型，并在几类复杂网络模型和几个实际网络中对该传播模型进行了模拟仿真，其结果与理论结果完全一致，验证了该模型的合理性。..在图的染色方面，我们研究了图的邻点（邻和）可区别的边(全)染色、全染色、无圈边（全）染色、均匀点荫度、线性荫度、边染色等，主要成果有：（1）证明了1-2-3猜想在树染色的情况下是成立，并首次提出tree-coloring 2-weighting问题；（2）获得了平面图的邻和可区别的全色数的一个上界；（3）首次提出图的均匀点荫度的概念，并获得了平面图的均匀点荫度的一个上界，提出了两个猜想；（4）改进了一些有关平面图的全染色、线性荫度和边染色的结果。