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

基本信息
批准号:11571180
项目类别:面上项目
资助金额:50.00
负责人:许宝刚
学科分类:
依托单位:南京师范大学
批准年份:2015
结题年份:2019
起止时间: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-有界猜想及色数与禁用导出圈关系方面取得了一些新结果,我们还在图的划分问题上取得了一些进展。

项目成果
{{index+1}}

{{i.achievement_title}}

{{i.achievement_title}}

DOI:{{i.doi}}
发表时间:{{i.publish_year}}

暂无此项成果

数据更新时间:2023-05-31

其他相关文献

1

基于多色集合理论的医院异常工作流处理建模

基于多色集合理论的医院异常工作流处理建模

DOI:
发表时间:2020
2

基于直观图的三支概念获取及属性特征分析

基于直观图的三支概念获取及属性特征分析

DOI:10.3778/j.issn.1673-9418.2104120
发表时间:
3

“阶跃式”滑坡突变预测与核心因子提取的平衡集成树模型

“阶跃式”滑坡突变预测与核心因子提取的平衡集成树模型

DOI:10.16031/j.cnki.issn.1003-8035.2019.05.04
发表时间:2019
4

WMTL-代数中的蕴涵滤子及其应用

WMTL-代数中的蕴涵滤子及其应用

DOI:10.11897/SP.J.1016.2018.00886
发表时间:2018
5

Fe-Si合金在600℃不同气氛中的腐蚀

Fe-Si合金在600℃不同气氛中的腐蚀

DOI:DOI: 10.11902/1005.4537.2013.169
发表时间:2014

许宝刚的其他基金

批准号:10671095
批准年份:2006
资助金额:23.00
项目类别:面上项目
批准号:11171160
批准年份:2011
资助金额:38.00
项目类别:面上项目
批准号:10371055
批准年份:2003
资助金额:18.00
项目类别:面上项目
批准号:12126339
批准年份:2021
资助金额:20.00
项目类别:数学天元基金项目
批准号:10001035
批准年份:2000
资助金额:5.50
项目类别:青年科学基金项目

相似国自然基金

1

关于图染色及相关问题研究

批准号:10971198
批准年份:2009
负责人:卜月华
学科分类:A0409
资助金额:29.00
项目类别:面上项目
2

图的全染色猜想及相关问题的研究

批准号:11101345
批准年份:2011
负责人:陈美润
学科分类:A0409
资助金额:23.00
项目类别:青年科学基金项目
3

关于Steinberg猜想及其相关问题的研究

批准号:11571168
批准年份:2015
负责人:周国飞
学科分类:A0409
资助金额:50.00
项目类别:面上项目
4

图的Brouwer猜想及相关问题的研究

批准号:11701102
批准年份:2017
负责人:李建平
学科分类:A0409
资助金额:21.00
项目类别:青年科学基金项目