图的小彩虹连通数与彩虹连通数上界的研究

From 2006, Charchand et al. introduced the rainbow connection number rc(G), the problem about coloring goes again into a summit. Relative to classic χ(G) and χ'(G), the history of research for rc(G) is not very long, there is still many unknown fields to be excavated. The project will probe into the structure of graphs and look for the conditions for edge number and minimum degree for graphs with small rainbow connection number, according to the theory of rainbow connection number and the technique of probability especially the structure of graphs; We will decide whether a graph with rc(G)=2 can be colored by 3 or 4 colors in polynomial time, furthermore, decide whether a graph with rc(G)=k can be colored by o(n) colors in polynomial time; The relation about minimum degree(sum) and the rainbow connection number are researched by joining the two big lemmas-Regular lemma and Local lemma, the function about minimum degree (sum) will be used to do the bound of rainbow number, and examples will be showed that the obtained bound can reach the best; The rainbow connection number of graphs with bridges are researched by resigning program and algorithm to consider especially bridges. The expected results of the project have positive academic significance for expanding the field of graph coloring, it also can be used in many fields such as network, environment, energy, electric and military, etc.

自2006年Charchand et al.引进了彩虹连通数rc(G)以来，图染色问题的研究又进入了一个高峰期。相对于经典的χ(G)和χ'(G)，彩虹连通数rc(G)还存在众多的未知领域有待挖掘。本项目根据彩虹连通和彩虹连通数的理论，利用概率特别是图的结构方法，探讨具有小彩虹连通数的图的结构，寻找图具有小彩虹连通数的边数与最小度条件；根据图的结构，判断能否用3或4种颜色在多项式时间内对一个rc(G)=2的图进行彩虹着色，进而判断能否用o(n)种颜色在多项式时间内对一个rc(G)=k的图进行彩虹着色；结合正则与局部引理，研究最小度(和)与彩虹连通数rc(G)的关系，用有关最小度(和)的表达式来做彩虹连通数的界，并举例子说明所得的界达到最好；运用设计程序与算法，充分考虑桥，研究有桥图的彩虹连通数。项目预期研究成果对拓展图的染色领域具有积极的学术意义，能应用在网络、环境、能源、电力、军事等领域。

图的染色问题是图理论研究非常有趣的重要内容，2006年Charchand et al.引进了一种新的色标¬—彩虹连通数，图染色问题的研究又进入了高峰期。彩虹连通数的有关定义来自于一个国家的重要信息必须受到安全保护这一背景。图G的一个k边染色是一个映射c:E(G)→C, 其中C是k种不同颜色的集合。令G是一个边染色图，如果图G中一条路的每条边都染有不同的颜色，则称这条路为图G的彩虹路。如果图G的任意两个顶点间都存在一条彩虹路，则称图为彩虹连通。如果一个边染色使图G彩虹连通，则称该染色为彩虹染色。称图G的彩虹染色所需的最小颜色数为图G的彩虹连通数，记为rc(G)。本项目研究了四方面的内容，首先找出了图具有小彩虹连通数的条件，然后考虑在多项式时间内彩虹染彩虹数为k的图，最后研究彩虹连通数与最小度(和)与及彩虹连通数与独立数的关系。本项目的研究目标是根据彩虹连通和彩虹连通数理论，深入探讨具有小彩虹连通数的图的结构，为促进彩虹连通数的研究起到积极的推动作用；将正则引理、局部引理两大引理相结合，研究独立数与彩虹连通数rc(G)的最佳关系，为图理论中的极值问题提供有效的方法；寻求研究有桥图的彩虹连通数的有效方法，为彩虹染色进一步深入的研究提供方法、技巧及理论上的支持。本项目解决下列几个关键科学问题，一是找出了边数条件和最小度条件使得图的彩虹连通数为k，可以掌握rc(G)=k的图的大致结构。二是找出了彩虹连通数与独立数的关系，是深入探讨彩虹连通、彩虹连通数与其它参数间的关系的理论基础，成为解决彩虹连通及彩虹连通数问题的重要工具和手段。本项目的特色和创新在于为研究彩虹连通数尤其是彩虹连通数比较小的图的刻划提供了理论依据。根据图的结构找出彩虹连通数 rc(G)与最小度(和)及独立数的表达式，为后续的彩虹连通数的研究提供强有力的工具。通过设计程序等方法了解图的结构，为染色问题的研究提供了染色方法与分析技巧，为解决彩虹连通数问题提供新思路和新途径。