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

项目名称： 图的染色问题及其在网络中的应用

项目编号： No.11201440

项目类型： 青年科学基金项目

立项/批准年度： 2013

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

项目作者： 刘彬

作者单位： 中国海洋大学

项目金额： 22万元

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

中文关键词： 图的染色；全染色；列表染色；线性荫度；复杂网络

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

英文关键词： Graph Coloring；Total Coloring；List Coloring；Linear Arboricity；Complex Networks