图设计的相交数问题与染色问题研究

Graph design is one of the important task of combinatorial design theory. The construction methods and existence of graph design has aroused wide attention from the domestic and foreign graph theory scientist and combinatorial design expert. The intersection problem of graph design has important application in statistics and closely related to the large set of combinatorial design theory. The coloring problem is a classical problem in graph theoretical. It has a wide application background and a long research history, and it is also one of the fundamental and important problems in combinatorial design theory．The project intends to study intersection problem and coloring problem of graph design. Specifically, the research content is outlined as follows: (1) The project continues preliminary work to systematic research on intersection problem for group divisible design, maximum packing design and some classes graph designs. In addition, the project intends to study the existence of some classes of edge balanced H(3)-design (hypergraph H(3)-decomposition of the complete hypergraph Kv(3)）and some classes of graph divisible design using the algebraic tools and methods of combinatorial design. (2) The project intends to study the existence of uncolorable, k-coloring, k-regular coloring, equitable k-coloring problem of some classes graph designs combining with the methods of graph theory, algebraic graph theory and combinatorial design, where the main emphasis of our research is the case of k=2,3. These problems are recent hot issues concerned by graph theory scientist and combinatorial design expert. So this topic has important theoretical significance and practical application value.

图设计是组合设计的重要研究内容之一，对图设计的构造方法和存在性问题的研究引起了国内外组合设计与图论专家的广泛关注。图设计的相交数问题在统计学中有着重要的应用，与组合设计中的大集密切相关。染色问题是图论中的经典问题，有很强的应用背景和悠久的研究历史，同时也是组合设计理论中的一项重要研究课题。本课题拟研究图设计的相交数问题和染色问题：（1）继续前期工作，拟系统研究可分组设计、最大填充设计、几类图设计的相交数问题。另外，利用代数工具和组合设计的构造方法拟研究几类边平衡的H(3)-design(完全超图的超图分解)和几类图可分设计的存在性。2）结合图论、代数图论、组合设计中的方法研究几类图设计的不可着色性、k-染色、k-正则染色、平衡k-染色等的存在性问题，重点研究k=2,3情况。这些问题都是组合设计与图论领域共同关注的热点问题，从而本课题有重要的理论意义和实际应用价值。

图设计中的相交数问题不仅是组合设计理论的基本问题，而且在统计学中有广泛的应用背景。（1）本项目深入研究了可分组设计（GDD）的存在性和相交数问题。给出了所需的可分组设计的构造法，构造出可分解可分组设计4-RGDD的相交数递归构造法和可分组设计的flower相交数构造法，解决了组型为4^u的可分组设计相交数问题（此问题又等价于Steiner 系统S(2,4, 4u)具有公共平行类的相交数问题）和组型为3^u的可分组设计的flower相交数问题。（2）本项目深入研究了图设计的构造法、存在性及其相交数问题。给出了完全多部图的kite图分解和带洞kite图分解的存在性，构造出kite图设计和带洞图设计的相交数递归构造法，解决了两类kite-GDD的相交数问题。（3）染色问题是图论中的经典问题，有很强的应用背景和悠久的研究历史，同时也是组合设计理论中的一项重要研究课题。本项目研究了广义 Peterson 图等特殊图的染色问题、控制数问题和标号问题等，扩大了染色问题和控制数问题的研究结果。