图的双临猜想及相关的着色问题-东篱科研大数据发现系统（DRDS）

位置：立项数据库 > 立项详情页

图的双临猜想及相关的着色问题

项目名称：图的双临猜想及相关的着色问题
项目类别：地区科学基金项目
批准号：11161046
申请代码：A011602
项目来源：国家自然科学基金
研究期限：2012-01-01-2015-12-31

项目负责人：宝音都仍
负责人职称：教授
依托单位：新疆大学
批准年度：2011

中文摘要：

一个图G被称作双临界，若对G的每两个相邻顶点u, v, G-u-v的色数等于G的色数减2。1968年Erdos和Lovasz提出每个双临界图是一个完全图, 现被称作双临界猜想。事实上，它是Erdos-Lovasz Tihany 猜想的特殊情形。最近，Kawrabayshi, Pedersen和Toft提出双临界Hadwiger猜想，每个双临界k-色图包含一个 -minor。因双临界猜想与著名的Hadwiger猜想有紧密联系，对双临界猜想及相关着色问题的研究有所突破将对图的着色理论和图论的其它分支产生深远影响。我们将围绕以上几个猜想展开研究，对它们给出部分回答。此外，我们将引进与图的双临界性密切相关的若干新的概念，如色可划分图，随机k-可着色图等，进而彻底刻画出这类图。

中文主题词：双临界图；色数；着色数；控制数；距离

英文摘要：

double-critical graphs；chromatic nubmer；coloring number；domination number；distance

英文主题词： double-critical graphs；chromatic nubmer；coloring number；domination number；distance

结论摘要：

我们主要研究双临界猜想及相关的着色问题。本项目执行过程中我们提出了两类图色可划分图与随机k-可着色图，它与双临界图的研究紧密相关。我们提出了列表双临界图或者是列表边双临界图的定义，证明了一个图是列表双临界图或者是列表边双临界图，则它是完全图。我们还否定了群着色的Hadwiger-型猜想，证实了一个弱形的列表荫度猜想，得到了Grundy数的两个新的上界，证明了一个图的着色数不超过它的Randic指标的2倍，得到了无三角形图的色数的一个上界。此外，我们还解决了有关图的控制数，邻近度，远离度的若干猜想和公开问题。

成果综合统计