图的彩虹（顶点）连通的若干问题的研究

Graph coloring is a central topic in graph theory. The rainbow connection number can be viewed as a variation of classic graph coloring, and has wide applications in information security and so on. Since the topic was introduced, it has attracted the attention of many scholars in the field of graph theory. As a natural generalization, Krivelevich and Yuster proposed the concept of rainbow vertex-connection of graphs. Although the study of rainbow (vertex-) connection has already yielded a lot of results, there still remain many important problems to be resolved. In this project, we focus on the following three problems: Take advantage of related theories of dominating set, study the relationship between the rainbow vertex-connection number of a graph and its diameter; Start from the forbidden subgraphs of line graphs, explore the relationship between the rainbow connection number of a graph and that of its line graph; Take advantage of the structure of a 2-connection graph, discuss the open problem of the absolute value of the difference between its rainbow vertex-connection number and rainbow connection number. We believe that the project will help us have a deeper understanding of the rainbow (vertex-) connection.

图的着色一直以来都是图论中的一类中心问题。图的彩虹连通不仅可以看作是经典图着色的一种变形，而且在信息安全等方面具有广泛的应用。因此，图的彩虹连通自提出之后，受到了国内外许多图论学者的关注。作为一个自然的推广，Krivelevich和Yuster提出了图的彩虹顶点连通的概念。虽然彩虹（顶点）连通的研究已经取得丰富的结果，但是仍有很多重要的问题急需解决。本项目重点关注如下三个问题：一、利用控制集的相关理论，探索图的彩虹顶点连通数与其直径的关系；二、从线图的禁用子图结构出发，探讨线图与其原图的彩虹连通数之间的关系；三、利用2-连通图的结构特点，探讨“2-l连通图的彩虹顶点连通数与彩虹连通数的差值的绝对值”这一公开问题。本项目有望帮助我们更深入更全面地认识图的彩虹（顶点）连通。

图的着色一直以来都是图论中的一类中心课题。2008年，以信息安全为应用背景，Chartrand等人引入并研究了彩虹连通数。此后，有学者陆续定义了图的彩虹顶点连通数、单色（顶点）连通数等一系列图参数，它们被统称为图的着色连通数。关于图的着色连通的研究已成为图论研究的一个热点。本项目主要研究了图的彩虹顶点连通和单色顶点连通。除此之外，在图的动态着色方面也取得了一些进展。主要研究结果如下：1.对随机图的彩虹顶点连通数和单色顶点连通数进行了研究，利用Bollobás关于随机图的直径的相关结果确定了随机模型G(n,p)下“彩虹顶点连通数不大于给定常数”和“单色顶点连通数不小于给定函数”的紧阈值函数。2.通过结构分析分别刻画了零控制数与其全零控制数相等的单圈图，以及全零控制数与其连通零控制数相等的树和单圈图。