图的边覆盖染色

项目名称： 图的边覆盖染色

项目编号： No.11426213

项目类型： 专项基金项目

立项/批准年度： 2015

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

项目作者： 李金波

作者单位： 中国矿业大学

项目金额： 3万元

中文摘要： 图的染色问题是一个热门的研究课题。其中，图的边染色在信息科学、计算机科学中有着重要的应用。图的边覆盖染色是由Gupta首先提出来的。苗连英研究了边覆盖染色的性质，并对图关于边覆盖染色的分类问题给出了一些结果。Hilton给出了关于多重图边覆盖的一些结论。 本项目主要研究图的边覆盖染色及其相关问题。我们的研究主要分如下几个方面：对某些特殊的图类进行边覆盖染色，给出其边覆盖色数的确切值或上下界；边覆盖临界图的性质；著名的Gupta猜想；图关于边覆盖染色的分类问题。在现实生活中，很多优化问题、网络设计问题，如计算机网络中的文件传输、信号设计等，都与图的边覆盖染色有关。本项目研究的课题涉及到组合数学、优化理论、计算机科学等多个领域，问题的解决将对计算机科学、信息科学的发展和创新有重要的影响。

中文关键词： 图；染色；Gupta猜想；分类；边覆盖染色

英文摘要： The colorings of graphs are hot research topics. Edge colorings have important applications in information science and computer science. The edge cover coloring is first proposed by Gupta. Miao Lianying studied the properties of the edge cover coloring of graphs, gave some results of the classification of graphs on edge cover coloring. Hilton gave some conclusions on the edge cover coloring of some multigraphs. We mainly study the edge cover coloring of some graphs and some related problems in this project. Our project mainly contain the following aspects: give the exact value or the upper and lower bounds of its edge cover chromatic number for some special classes of graphs; the properties of the edge cover critical graphs; the famous Gupta Conjecture; classification of graphs on edge cover coloring. In our real life, many optimization problems, network design problems, such as file transfer of computer networks, signal design, etc., have relation with the edge cover coloring of graphs. This project involves multiple areas, such as, combinatorics, optimization theory, computer science, etc, the solutions of these problems will play an important role in the development and innovation of computer science and information science.

英文关键词： graph；coloring；Gupta Conjecture；classification；edge cover coloring