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

结题报告

项目介绍

AI项目解读

基本信息

批准号：
11571180
项目类别：
面上项目
资助金额：
50.0万
负责人：
许宝刚
依托单位：
南京师范大学
学科分类：
A0409.图论及其应用
结题年份：
2019
批准年份：
2015
项目状态：
已结题
起止时间：
2016-01-01 至2019-12-31

项目参与者：
王晓谦；董伟；万敏；张莹丽；韩徐曦；王巧芸；肖然；
关键词：
导出子图图的色数图的团数树

项目摘要

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-有界猜想及色数与禁用导出圈关系方面取得了一些新结果，我们还在图的划分问题上取得了一些进展。