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

刘利群,陈祥恩

(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的每个顶点随机独立的挑选它的一条关联边用新颜色a重染.这时,边e=uv被新颜色a重染的概率是

第三步在第二步完成后,另取一种新颜色b,再对G的每个顶点随机独立的挑选它的一条关联边用新颜色b重染.注意:新颜色b可能覆盖新颜色a.

第四步在第三步完成后,另取一种新颜色c,再对G的每个顶点随机独立的挑选它的一条关联边用新颜色c重染.注意:新颜色c可能覆盖新颜色a,b.

下面将证明以下两点成立的概率为正:

1.着色仍然正常即没有相邻两条边或相邻的两点着色相同或相关联的点与边着色相同;

2.着色是邻点可区别的即对任意两点u,v∈V(G)(1≤d(u,v)≤2),有C(u)̸=C(v).为此,定义如下坏事件:

(I)对每对相邻的边{e,f∈E(G)},令Ae,f表示e和f被染成同种颜色的事件.

(II)对每一条边

令Bu,v表示u和v的关联边是正常着色且C(u)=C(v)的事件.

下面证明上述事件都不发生的概率为正.

构造相关图D,其中D的顶点是以上二种类型的所有事件,设EX,EY是D的两个顶点(每个X,Y是一对相邻边,或者是和一条边相邻的所有边及其这条边本身.EX和EY是相邻的当且仅当X和Y至少包含一条公共边.由于EX的每个事件发生依赖于X的边,从而D是事件的相关图.

首先,需要计算每个坏事件发生的概率,有以下三条成立:

1)对类型(I)的每个事件Ae,f,有

[1]张忠辅,陈祥恩,李敬文,等.关于图的邻点可区别全染色[J].中国科学:A辑,2004,34(5):577-583.

[2]Zhang Zhongfu,Chen X iang′en,Li Jingwen,et al.On the ad jacent vertex distinguishing total coloring of graph[J].Science in China:Ser A,2005,48(3):289-299.

[3]Zhang Zhongfu,Yao Bing.A note on the ad jacent vertex distinguishing total chromatic number of graph[J]. Journal of Lanzhou Jiaotong University:Natural Science,2006,23(6):143-145.

[4]M olloy M,Reed B.A bound on the total chromatic number[J].Combinatorica,1998,18:241-280.

[5]晁福刚,张忠辅,强会英.图的邻点可区别全色数的一个上界[J].纯粹数学与应用数学,2010,26(1):91-95.

[6]A lon N,Spencer J.The Probabilistic Method[M].New York:W iley,1992.

[7]M olloy M,Reed B.G raph Coloring and the Probabilistic M ethod[M].New York:Springer,2002.

[8]Yap H P.Total Coloring of G raphs[M].New York:Springer,1996.

[9]Bondy J A,M urty U SR.G raph Theory with App lications[M].London:London M acm illan Press,1976.

[10]Dietel R.G raph Theory[M].New York:Springer,1997.

On an upper bound for ad jacen t vertex d istinguish ing total ch rom atic num ber of graphs

Liu Liqun1,Chen Xiang′en2

(1.College of In form ation and M athem atics,Yangtze University,Jingzhou 434023,China; 2.College of M athem atics and In form ation Science,Northwest Norm al University,Lanzhou 730079,China)

A proper total coloring of the graph G is called ad jacent vertex distinguishing total coloring,for any two ad jacent vertices u,v∈V(G),we have C(u)̸=C(v),where C(u)is called color set of vertex u.Inthis paper, we study the upper bound on the ad jacent vertex distinguishing total chromatic number.Δ+C+20is a good conclusion of the upper bound on the ad jacent vertex distinguishing total chrom atic number of graphs up till now.By probability m ethod,we obtained the conclusion that a upper bound on the ad jacent vertex distinguishing total chrom atic number isΔ+C+3 in som e condition in this paper.

ad jacent vertex distinguishing total coloring,ad jacent vertex distinguishing total chrom atic number,upper bound

O157.5

A

1008-5513(2012)06-0744-05

2011-12-16.

国家自然科学基金(61163037,61163054).

刘利群(1977-),硕士,讲师,研究方向：图论及其应用.

2010 M SC:05C15