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

项目名称： 图的小彩虹连通数与彩虹连通数上界的研究

项目编号： No.11461030

项目类型： 地区科学基金项目

立项/批准年度： 2015

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

项目作者： 董九英

作者单位： 江西财经大学

项目金额： 36万元

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

中文关键词： 彩虹连通；彩虹连通数；控制集；度（和）条件；桥

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

英文关键词： rainbow connection;rainbow connection number;dominate set;degree(sum) conditions;bridge