An Upper Bound for the Adjacent Vertex Distinguishing V-Total Chromatic Number of Graphs

图染色是图论的主要研究方向之一，而邻点可区别染色^[1]是图染色的主要研究内容之一.用概率方法来确定图染色中色数的界是一种新颖的方法，1974年Erdös首先引入概率方法证明Ramsey数r(k，k)≥2^k/2.目前用概率方法得到的一些结果可参考文献[2-3].

对于一般图的邻点可区别全色数并不容易确定，后来学者们又提出了弱染色的概念.若一个满足邻点可区别全染色的图可以出现不正常点染色，则称图染色为邻点可区别Ⅴ-全染色；若一个满足邻点可区别Ⅴ-全染色的图可以出现点与其关联边染同色，则称图染色为邻点可区别Ⅵ-全染色.分别用χ_at^v(G)，χ_at^vi(G)表示图G的邻点可区别Ⅴ-全色数，邻点可区别Ⅵ-全色数，显然有χ_at^vi(G)≤χ_at^v(G).关于弱染色的一些结果见文献[4-6]，文献[7]得到了邻点可区别Ⅵ-全色数的一个上界.文中未加说明的术语见文献[8].

定理1^[7] 对于简单图G，若$\delta \geqslant 150\sqrt {\Delta {\rm{ln}}\Delta } $，则

本文研究了图的邻点可区别Ⅴ-全染色，并应用Lovász局部引理得到了图的邻点可区别Ⅴ-全色数的一个上界.

定理2 对于简单图G，若$\delta \geqslant 75\sqrt {\Delta {\rm{ln}}\Delta } $，则

由于

所以当$\delta \geqslant 75\sqrt {\Delta {\rm{ln}}\Delta } $时，有

这个结果显然要比定理1的结果更优.

定理2的证明

在证明定理2之前，首先给出相关的引理以及几个不等式：

引理1^[9] 若G是简单图，则它的边色数不超过Δ+1.

引理2^[10-11] (Lovász局部引理)考虑(典型的坏的)事件的集合ε={A₁，A₂，…，A_n}，对每一个A_i，都存在D_i⊆ε(D_i可以为空)，使得每个A_i与ε-(D_i∪A_i)互相独立.若有实数x₁，x₂，…，x_n∈[0，1)使得对每个1≤i≤n有

则ε中所有事件都不发生的概率至少是

文中所用到的不等式：

(ⅰ)当a，b∈N时，$\left( {\begin{array}{*{20}{l}} a \\ b \end{array}} \right) \leqslant {\left( {\frac{{ea}}{b}} \right)^b}$；

(ⅱ)当$x \in \left( {0,\frac{1}{{10}}} \right)$，y≥0时，(1-x)^y≤e^-xy，(1-x)^y≥e^-2xy；

(ⅲ)当x≥2时，${\left( {1 - \frac{1}{x}} \right)^x} \geqslant \frac{1}{4}.$.

下面给出定理2的具体证明过程：

定理2的证明 首先，由引理1得，可以用Δ+1种颜色对图G的边正常着色，再用一种新色对所有点进行着色，然后再对G的每条边及顶点独立地用$N = \sqrt {\Delta {\rm{ln}}\Delta } $中的一种颜色以$p = \frac{1}{{10\Delta }}$的概率随机均匀地重新着色.为了保证图G是正常的邻点可区别Ⅴ-全染色，需满足以下条件：

(ⅰ)正常边染色——任意两条相邻边不能染同色；

(ⅱ)关联元素染色正常——任意点与其关联边不能同色；

(ⅲ)邻点可区别——任意相邻点的色集合均不同.

第一步，定义如下坏事件：

(ⅰ)对每一对相邻的边e₁，e₂，令E_A表示e₁和e₂染同种颜色的事件；

(ⅱ)对每条边e，令E_B表示e和其某一端点染同色的事件；

(ⅲ)任意相邻点u和v，其中d(u)=d(v)，令E_C表示点u和v的色集合满足C(u)=C(v)的事件.

第二步，计算坏事件发生的概率：

若事件E_A发生，则相邻边e₁与e₂必染同种新色，边e₁染新色的概率为Np，边e₂染与e₁相同颜色的概率为p，于是事件E_A发生的概率为Np².同理，事件E_B发生的概率为2Np²，因此

若事件E_C发生，则

令

是一个固定集合，则|C|=d，于是可设C中有i种新颜色，d-i种旧颜色.对于每条边染某种新色的概率为p，不染任何新色的概率为1-Np，因此事件E_C发生的概率为：

由于当$\delta \geqslant 75\sqrt {\Delta {\rm{ln}}\Delta } $时，$Np ＜ \frac{1}{{10}}$都成立，故由引理2中的不等式(ⅰ)，(ⅱ)得：

把$N = \sqrt {\Delta {\rm{ln}}\Delta } $，$p = \frac{1}{{10\Delta }}$代入(1)式，则

由于$75\sqrt {\Delta {\rm{ln}}\Delta } \leqslant \delta \leqslant \Delta $，则

于是

因此

第三步，计算相关事件数

首先构造图D，其结点为两种类型的所有事件，其中两个结点E_X和E_Y相关，当且仅当X和Y包含一个公共元素.由于每个事件E_X的发生，仅依赖于X的元素，故D是上述事件的相关图.

各事件之间的具体相关数见表 1，其中每个事件X与其他事件的相关数均取它的上界.

注释：事件E_A包括两条边e₁，e₂，和每一条边相交的边数至多有2Δ条，因此事件E_A与事件E_A的相关数不超过4Δ；而每条边最多与其相关联的两个点颜色相同，因此事件E_A与事件E_B的相关数不超过4；事件E_A包括3个点，当事件E_A与事件E_C包括1个公共点u时，与点u色集合相同的邻点不超过Δ，于是事件E_A与E_C的相关数不超过3Δ；同理可得其他相关事件数.

第四步，构造常数证明不等式：

设$\frac{1}{{50\Delta }}\sqrt {\frac{{{\rm{ln}}\Delta }}{\Delta }} ,\frac{1}{{25\Delta }}\sqrt {\frac{{{\rm{ln}}\Delta }}{\Delta }} ,\frac{1}{{5{\Delta ^2}}}$分别表示与事件E_A，E_B，E_C相关的常数.

第五步，计算坏事件不发生的概率为正：

若要应用Lovász局部引理证明坏事件不发生的概率为正，需证明以下三个不等式成立：

根据不等式${\left( {1 - \frac{1}{x}} \right)^x} \geqslant \frac{1}{4}$对x≥2均成立，于是有

要想证明(2)式，只需证明

即证

上式显然成立，于是(2)式成立，同理可证明(3)式成立.

由于当$x \in \left( {0,\frac{1}{{10}}} \right)$，y≥0时，(1-x)^y≥e^-2xy，因此有

下面证明(4)式，只需证明

即证

(5) 式等价于

由于$\delta \geqslant 75\sqrt {\Delta {\rm{ln}}\Delta } $，于是$\frac{1}{{25}}d\sqrt {\frac{{{\rm{ln}}\Delta }}{\Delta }} \geqslant 3{\rm{ln}}\Delta $，因此只需证明

当Δ≥13时，(6)式显然成立，故(4)式成立，因此有