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

项目名称： 图的新染色问题以及在复杂网络中的应用

项目编号： No.11271006

项目类型： 面上项目

立项/批准年度： 2013

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

项目作者： 吴建良

作者单位： 山东大学

项目金额： 68万元

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

中文关键词： 复杂网络；社团结构；平面图；全染色；均匀点荫度

英文摘要： 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.

英文关键词： complex networks；community structure；planar graph；total coloring；equitable vertex arboricity