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

项目名称： 图的双临猜想及相关的着色问题

项目编号： No.11161046

项目类型： 地区科学基金项目

立项/批准年度： 2012

项目学科： 数理科学和化学

项目作者： 宝音都仍

作者单位： 新疆大学

项目金额： 40万元

中文摘要： 一个图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