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

图的染色问题是图论研究的基本问题之一，在网络优化和大规模集成电路的设计等方面有重要的应用。Vizing(1964)和Behzad(1965)各自独立提出著名的全染色猜想，这个猜想尚未被完全证明，是图论中公认的一个难题。近年，张忠辅等人提出与全染色密切相关的邻点可区别边染色和邻点可区别全染色两个概念。本项目将研究几类图的全色数、邻点可区别边色数和邻点可区别全色数。包括：（1）确定折叠立方体图、可扩立方体图、Mobius立方体图、立方体的次方图等重要网络拓扑结构图的全色数、邻点可区别边色数和邻点可区别全色数；(2)确定度较大的图的邻点可区别边色数和邻点可区别全色数的上界；（3）揭示笛卡尔乘积图的邻点可区别边色数和邻点可区别全色数与因子图的各指标之间的关系。这些问题的研究不仅有重要的理论意义而且有实际应用背景。

全染色猜想迄今为止，仍然没有得到证明，也没有较好的上界。本项目确定了折叠立方体图、可扩立方体图、扭立方体图的全色数和邻点可区别全色数。其中，折叠立方体图和可扩立方体图的相关结论已被SCI杂志Ars Combinatoria收录。同时，我们研究了广义myceilski图的全色数，证明它的全色数满足全染色猜想。该结论被著名SCI杂志Discrete Mathematics收录。在研究广义mycielski图的过程中，我们提炼出一个问题：当图中只有一个最大度点时，全染色猜想是否成立? 若成立，那么我们可以由此得出最大度加四是任意图的全色数的一个上界。但由于确定一个图的全色数的问题是NP困难的，目前我们尚未证明只有一个最大度点的图满足全染色猜想。