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

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

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