刘利群,陈祥恩

(1.长江大学信息与数学学院,湖北 荆州 434023;2.西北师范大学数学与信息科学学院,甘肃 兰州 730079)

关于图的邻点可区别全色数的上界研究

刘利群1,陈祥恩2

(1.长江大学信息与数学学院,湖北 荆州 434023;2.西北师范大学数学与信息科学学院,甘肃 兰州 730079)

图G的邻点可区别全染色是指G存在一个正常全染色f使得任意相邻两点有不同的色集合.本文主要研究邻点可区别正常全色数的上界,目前邻点可区别全染色的一个较好的上界是∆+C+20,本文用概率方法改进了这个结果,得到了邻点可区别全色数的一个较小上界∆+C+3.

邻点可区别全染色;邻点可区别全色数;上界

1 引言

染色问题是图论中具有重要实际意义和理论意义的研究课题之一.1965年,Bahzad和Vizing各自独立提出了图的全染色的概念和猜想.2004年,文献[1-2]提出了图的邻点可区别全染色的概念和猜想.文献[3-4]对图的全染色作了进一步研究,得到了一些较好的结果.文献[5]得到了邻点可区别全染色的一个上界∆+C+20.本文尝试通过应用局部引理,得到了邻点可区别全色数的一个较小的上界∆+C+3.

下面给出将要用到的一些概念与定理.

定义1[1]G(V,E)是阶至少为2的连通图,k是正整数,f是从V(G)∪E(G)到{1,2,···,k}的一个映射.对任意u∈V(G),记

2 主要结果及证明

定理1 设G(V,E)是连通图,若

证明 假设图G(V,E)已给出,分以下四个步骤对图G的边进行染色:

第一步由引理3,可先用∆(G)+C种颜色对G进行正常全染色.

第二步取一种新颜色a,对G的每个顶点随机独立的挑选它的一条关联边用新颜……