彩虹（顶点）连通数的界和极图问题的研究

Graph coloring is one of the most important topic in graph theory, and lots of open problems, for example the four color problem, are hot problems studied by many researchers at home and abroad. Connectivity of a graph is one of the most important properties in graph theory, and rainbow connection is a strengthening of the classical connectivity and an important graph coloring problem. Besides its theoretical interest in combinatorial mathematics, rainbow connection also finds practical applications in many problems of network security. . The main aim of this project is to study the upper bounds of rainbow connection number and rainbow vertex-connection number of k-connected graphs, and characterize 2-connected extremal graphs of those upper bounds. Using the construction properties of k-connected graphs, extremal graph theory and graph coloring theory, we will study the upper bounds of rc(G) and rvc(G) and characterize the 2-connected extremal graphs from the angle of algorithm. By combining the classical methods in graph theory and probability method, we will study the relation between the rainbow (vertex-)connection number and connectivity. Since computing the rainbow (vertex-)connection number is an NP-hard problem, the study of the upper bounds of rainbow (vertex-)connection number is a meaningful work and attracts interesting of many researchers.

图染色问题是图论中最重要的研究课题之一，如四色问题等很多图染色的公开问题一直是国内外众多学者的研究热点问题。图的连通性是图论中最重要的性质之一，而图的彩虹连通性是经典连通性概念的一种加强，也是一个重要的染色问题。彩虹连通性不仅在组合数学中有重要的理论意义，而且在网络安全等领域有着广泛的实际应用背景。. 本项目旨在研究k-连通图彩虹连通数和彩虹顶点连通数的上界和刻划达到上界的2-连通极图。利用k-连通图的结构性质、极图理论和图染色理论来研究rc(G)和rvc(G)的上界；从算法角度来刻划达到上界的2-连通极图；将经典图论中的方法与概率方法相结合，来研究彩虹（顶点）连通数与连通度之间的关系。由于彩虹（顶点）连通数的计算是NP-困难问题，彩虹（顶点）连通数上界的研究是非常有意义的工作，也引起了众多研究者的兴趣。

图染色问题是图论中最重要的研究课题之一，如四色问题等很多图染色的公开问题一直是国内外众多学者的研究热点问题。图的连通性是图论中最重要的性质之一，而图的彩虹连通性是经典连通性概念的一种加强，也是一个重要的染色问题。彩虹连通性不仅在组合数学中有重要的理论意义，而且在网络安全等领域有着广泛的实际应用背景。. 本项目研究了2-连通图的完全彩虹连通数和完全彩虹2-连通数，并得到了它们的最优上界；给出了1-连通图的完全彩虹连通数的以其顶点数和割点数为参数的最优上界。为了得到彩虹连通数和彩虹顶点连通数之间的关系，我们研究了广义西塔-图和哈密尔顿图的彩虹连通数和彩虹顶点连通数。通过构造合适的染色方法，我们找到了彩虹连通数和彩虹顶点连通数达到上界的一些2-连通图类。本项目资助发表论文3篇，待发表2篇。