关于图的模染色数的上界

On the Upper Bound of Modular Chromatic Number of Graphs

摘要: 图的模染色是由邻点赋权导出的一种染色，是图的经典染色的一种推广。本文主要运用概率方法中的Lovasz局部引理，较大幅度地改进了关于图的模染色数的上界。

Abstract: The modular coloring of a graph is induced by the weights of neighboring vertices. It is a generalization of the classic graph coloring. In this paper, we obtain a general upper bound for the modular chromatic number of graphs by using the Lovasz Local Lemma. Our result improves previous exponential bound significantly.

1. 引言

本文考虑的图都是指简单无向图，常用的图论术语和记号我们都依照文献 [1]。近年来，由图的邻点或邻边的标号导出的染色成为了图论中的一个研究热点。其中一种称为k边权点染色的定义如下。设图G的顶点集和边集分别记为V(G)和E(G)，边集上有一个权函数 $\omega :E\left(G\right)\to \left\{1,2,\cdots ,k\right\}$。由ω导出的顶点染色

$\omega \left(x\right)={\displaystyle \underset{y\in N\left(x\right)}{\sum }\omega (\; x\; y\; )}$

若满足对任意的一条边xy，都有 $\omega \left(x\right)\ne \omega \left(y\right)$，则称ω为图G的一个k边权点染色。关于k边权点染色，Karonski，Luczak和Thomason提出了以下著名猜想 [2]。

猜想 (1-2-3猜想)。除了K₂的所有连通图G都存在一个3边权点染色。

关于1-2-3猜想，目前最好的部分结果是除了K₂以外的连通图都存在一个5边权点染色 [3]。受到1-2-3猜想的启发，各种不同的由邻点或邻边所导出的染色也被许多研究者提出和研究。综述文章 [4] 对此有非常详尽的介绍。比如，幸运标号 [5] [6] 就是对1-2-3猜想中的边权点染色的一种自然推广，可视为点权点染色，即由邻点的赋权之和导出的染色。

本文将研究由Okamoto，Salehi和Zhang提出的一种染色 [7]，称为模染色，是在幸运标号的概念的基础上再加上模运算得到的一种新的染色，其定义如下。设 $c:V\left(G\right)\to {{\rm Z}}_k$ 是图G的顶点集上的一个权函数，令

$\sigma \left(x\right)={\displaystyle \underset{z\in N\left(x\right)}{\sum }c\left(z\right)}.$

注意到上式的求和运算是在模k整数群Z_k中进行的。如果σ是一个恰当的染色，则c称为图G的一个模k染色。图G的模k染色数定义为最小的正整数k，使得存在图G上的一个模k染色，记作χ_m(G)。在文章 [7] 中，Zhang等人证明了对于无孤立点的图，其模染色数一定存在。并且，他们还给出了模染色数的如下两个上界。

定理1 ( [7])。设n阶图G的最大度为Δ，则

${\chi }_m\left(G\right)\le 2^n-2^{n-\Delta }.$

定理2 ( [7])。设n阶图G的染色数为χ，最大度为Δ，则

${\chi }_m\left(G\right)\le \Delta {\left(\Delta +1\right)}^{\chi +1}+1.$

上述两个上界关于图的阶数n都是指数关系，相信离最好的上界还有很大的距离。然后，根据Zhang的最新专著 [8]，自从模染色数的概念在2010年提出以来，未见有人得到更好的上界。

本文的主要目的是改进这个上界。我们采用的是一种概率的方法，运用Lovasz局部引理。关于Lovasz局部引理，可参见文献 [9]。Lovasz局部引理是证明某些组合结构的存在性的一种方法。以下我们记P(A)为事件A发生的概率。

引理1 (Lovasz局部引理 [9])。设 $A_1,A_2,\cdots ,A_n$ 是某概率空间中的事件。又假设对每个A_i，除了最多d个事件外，A_i与其它所有事件A_j都相互独立。并且 $P\left(A_i\right)\le p$ ( $\text{1}\le i\le n$ )。设e为自然对数的底，如果 $ep\left(d+\text{1}\right)<\text{1}$，则有

$P\left({\wedge }_{i=1}^n{\bar{A}}_i\right)>0.$

运用Lovasz局部引理，我们将证明如下结论。

定理3. 设n阶图G的最大度为Δ，则

${\chi }_m\left(G\right)\le \left[e\left(1+2\left(\Delta -1\right)+2{\left(\Delta -1\right)}^{\text{2}}+2{\left(\Delta -1\right)}^{\text{3}}\right)\right]+\text{1}.$

从上面的结论可见，我们的上界是关于Δ的一个3次多项式，这大幅度改进了原来的指数上界。

本文第2部分将给出定理3的证明，第3部分对进一步的研究提出了一些想法。

2. 模染色数的一般上界

固定一个整数k，我们令 $c:V\left(G\right)\to {{\rm Z}}_k$ 表示一个随机的顶点权函数，每个点的权值的选取是独立的，且是均匀的。即对每个顶点v，和对 $\text{1}\le i\le k$，都有 $P\left(c\left(v\right)=i\right)=1/k$。对每条边xy，我们定义坏事件 $A_{xy}=\left\{\sigma \left(x\right)=\sigma \left(y\right)\right\}$。由此定义，图G的模k染色的存在性等价于存在某个顶点的权函数，使得对所有的边，其相应的坏事件都没有发生。

为了证明我们的主要结果，还需要下面两个引理。

引理2. 设 $c:V\left(G\right)\to {{\rm Z}}_k$ 为一个随机的顶点权函数，又xy是图G的任意一条边，则

$P\left(A_{xy}\right)=\frac{1}{k}.$

证明：事件A_xy仅依赖于顶点x，y以及它们的邻点集，即仅依赖于 $S=\left\{x,y\right\}\cup N\left(x\right)\cup N\left(y\right)$。我们考虑在对顶点集合S赋权时，分为如下两步。第一步，先对S\{y}上的点赋权。此步之后，σ(y)的值就已经定下来了，因为其邻点均已经赋权。而σ(x)的值尚未确定，因为x还有最后一个邻点y尚未赋权。第二步，对y赋权。不管第一步的赋权情况如何，在第二步中，y总是有且仅有一种赋权方法使得 $\sigma \left(x\right)=\sigma \left(y\right)$。由于前面我们定义y的赋权取值是一个均匀分布，所以 $P\left(A_{xy}\right)=1/k$。 £

引理3. 设图G的最大度为Δ，又设 $\left\{A_{xy}|xy\in E\left(G\right)\right\}$ 为图G中关于每条边的坏事件的全体之集。则每个事件A_xy在除了最多 $d=2\left(\Delta -1\right)+2{\left(\Delta -1\right)}^{\text{2}}+2{\left(\Delta -1\right)}^{\text{3}}$ 个事件以外，和其它坏事件相互独立。

证明：给定一条边xy，考虑另外一条边x'y'。如果边xy与x'y'的距离大于2，则由定义有事件A_xy和A_x'y'是独立的。所以我们只需要计算到xy的距离小于或等于2的边的数目。从顶点x看，最多有 $\Delta -1$ 条边距离为0，最多有 ${\left(\Delta -1\right)}^{\text{2}}$ 条边距离为1，最多有 ${\left(\Delta -1\right)}^{\text{2}}$ 条边距离为2。从顶点y看，也一样。所以，总共最多有 $d=2\left(\Delta -1\right)+2{\left(\Delta -1\right)}^{\text{2}}+2{\left(\Delta -1\right)}^{\text{3}}$ 条边与xy的距离小于或等于2。因此，除了最多这d条边所对应的事件，A_xy与其它所有事件相互独立。 £

Lovasz局部引理给出了某一系列坏事件都不发生的概率为正的一个充分条件。为了应用Lovasz局部引理，我们在引理2中对每个坏事件发生的概率p给出了精确的计算，在引理3中则对相互独立的坏事件的例外事件的数目d给出了一个估计。有了这两个引理的准备，下面我们可以证明定理3。

定理3的证明：令 $k=\left[e\left(1+2\left(\Delta -1\right)+2{\left(\Delta -1\right)}^{\text{2}}+2{\left(\Delta -1\right)}^{\text{3}}\right)\right]+\text{1}$。则只需证明图G存在一个模k染色。

考虑顶点集上的一个随机权函数，要证明图G上存在一个模k染色，我们又只需证所有坏事件A_xy都不发生的概率是正的，即只需证下式

$P\left(\underset{xy\in E\left(G\right)}{\wedge }{\bar{A}}_{xy}\right)>0.$

由引理2，对每条边xy，相应的坏事件A_xy发生的概率都为常数 $p=1/k$。

再由引理3，

$ep\left(d+1\right)=e\cdot \frac{1}{k}\left(1+2\left(\Delta -1\right)+2{\left(\Delta -1\right)}^{\text{2}}+2{\left(\Delta -1\right)}^{\text{3}}\right)<1.$

由引理1 (Lovasz局部引理)，所有坏事件A_xy都不发生的概率是正的。 £

3. 结语

本文运用Lovasz局部引理，大幅度改进了关于模染色数的上界，可见概率方法的威力。但这个证明不是构造性的，因此如何给出一个确定性的模染色算法，使得k比较小，仍然值得研究。我们得到的是一个O(n³)的上界，这个上界是否可以继续改进到O(n²)甚至O(n)，有待进一步的研究。此外，我们很自然会问一个问题：若图G存在一个模k染色，则对 $l>k$，图G是否也有一个模l染色？这个问题从模染色的定义上看，并不容易回答。由我们的主要结果和证明方法，我们可以得到一个推论，对每个图G，都存在一个自然数k₀(G)，使得当 $k\ge k_0$ 时，图G都存在一个模k染色。

致谢

感谢匿名审稿人对本文初稿提出的宝贵意见。

基金项目

国家自然科学基金青年科学基金项目(11201496)，广东外语外贸大学引进人才科研启动项目(299-X5219228)，广东外语外贸大学横向项目(297-ZW200011)。