关于图染色的x-有界猜想及相关问题研究

Graph theory is a very important branch of discrete mathematics, and colorings and subgraph structures of graphs are always in the center of graph theory. The Strong Perfect Graph Theorem is one of the most important results of this century in graph theory. It says that if a graph contains neither odd cycles of length at least 5 nor their complements as induced subgraphs, then its chromatic number is the same as its clique number. Gyarfas (1975), and Sumner (1981) independently, proposed the following conjecture (we call it the x-bounded conjecture): for any given tree T, there exists a function f such that if a graph G does not contain T as an induced subgraph then x(G)<=f(w(G)), where x(G) and w(G) are the chromatic number and clique number of G respectively。The x-bounded problem is an extension to the perfect graph problem, and attracts a lot of attention of graph theorists from all over the world. We will study this conjecture and some other related problem.

图论是离散数学的一个重要分支，而图的染色理论和子图结构问题一直以来都是图论研究的核心问题。强完美图定理是本世纪最重要的图论研究成果之一，证明了如果一个图既不含长度至少为5 的奇圈又不含其补图做为导出子图，则该图的色数与团数相等。Gyarfas (1975) 和 Sumner (1981) 各自独立地提出了以下猜想（我们称之为 x-有界猜想）：任意给定一棵树 T，存在一个函数 f，使得当一个图 G 不含 T 做为导出子图时，x(G)<=f(w(G))，其中 x(G) 和 w(G) 分别表示 G 的色数和团数。x-有界问题是完美图问题的延伸与推广，是目前国际图论界最为关注的问题之一，有重要的理论意义和应用价值，我们将围绕这一猜想和相关问题展开研究。

图论是离散数学的一个重要分支，而图的染色理论和子图结构问题一直以来都是图论研究的核心问题。强完美图定理是本世纪最重要的图论研究成果之一，证明了如果一个图既不含长度至少为5 的奇圈又不含其补图做为导出子图，则该图的色数与团数相等。Gyarfas (1975) 和 Sumner (1981) 各自独立地提出了以下猜想（我们称之为 x-有界猜想）：任意给定一棵树 T，存在一个函数 f，使得当一个图 G 不含 T 做为导出子图时，x(G)<=f(w(G))，其中 x(G) 和 w(G) 分别表示 G 的色数和团数。x-有界问题是完美图问题的延伸与推广，是目前国际图论界最为关注的问题之一，有重要的理论意义和应用价值. 我们在 Gyarfas-Sumner x-有界猜想及色数与禁用导出圈关系方面取得了一些新结果，我们还在图的划分问题上取得了一些进展。