图的邻点强可区别V-全色数的一个上界

蔡学鹏，任佰通，冯苗苗



图的邻点强可区别V-全色数的一个上界

*蔡学鹏，任佰通，冯苗苗

（新疆农业大学数理学院，新疆，乌鲁木齐830052）

应用概率论中的Lovasz一般局部引理得出了图的邻点强可区别V-全色数的上界，证明了对阶数不小于3且不含孤立边的简单图的邻点强可区别V-全色数不超过49△，△≥5。

Lovasz一般局部引理；邻点强可区别全染色；邻点强可区别V-全染色

0 引言

随着计算机的飞速发展，信息化和数字化技术的不断进步，许多实际问题的数学模型使离散型结构上的数字化技术得到了更多人的关注。图的染色理论[1]作为离散数学的一个重要组成部分，自然得到了快速发展，因此受到了国际数学界与工程界越来越广泛的重视。Noga Alon在2002年数学国际大会上作了“离散数学方法与挑战”的大会报告后，图的染色成为一个很活跃、很新颖的研究邻域。1993年A.C.Burris在他的博士论文中提到了点可区别正常边染色(也称强边染色)的概念[2]，此后P.N.Balister等人撰文[3]对该问题进行了深入的讨论，有关许多深入的结果都在国际权威杂志上刊出。在无线通讯网络中，为了防止网络中不同的长点之间信号频率的共振，必须保证不同站点之间拥有不同的通讯频率，无线传感器网络中相邻点通信冲突问题；交通运输中危险品运输的配送调度安全问题等，为了解决此问题，张忠辅教授首次提出了邻点可区别正常边染色[4]的概念，这一问题与点可区别边染色的研究具有相同的难度，因此国内外专家对此问题作了大量研究。2004年张忠辅教授在邻点可区别正常边染色的基础上提出了邻点可区别全染色[5]的概念，2007年又提出了邻点强可区别全染色[6]的概念。2010年程辉等在邻点强可区别的基础上提出了邻点强可区别EI-全染色[7]和邻点强可区别V-全染色[8]的概念。

图染色理论中对于常见的特殊图，如路图、圈图、星图、扇图和轮图等，其染色数可以根据群染法、反证法和构造函数等方法得出确定的结果。对于一般图而言，上述方法却不再合理。而应用概率论中的Lovasz一般局部引理，可以很巧妙地得出一些不同类型的图染色的上界，该方法在文献[12-15]中有一些应用结果。本文在邻点强可区别全染色的概念中，弱化其中的一个条件，即相邻点可以染同色，从而得出了图的邻点强可区别V-全色数的上界。

1 预备知识

为的邻点强可区别全色数。

为的邻点强可区别V-全色数。该定义将定义1中的条件1)弱化了，即相邻点可以染同色。

2 主要结论

1) 边染色是正常的，既没有两条相邻的边染成同色；

2) 点和边的染色是正常的，即任意一条边与他的悬挂点染不同颜色；

3) 色集合是正常的，即任意相邻两点的色集合不同，这里的色集合为该点的颜色，与他关联边的颜色，以及与他相邻点的颜色所组成的集合。下面将分三步完成该定理的证明。

第一步：定义以下三种类型的坏事件

如果坏事件1，2，3不发生的概率为正，即说明坏事件不发生是可能的，则称上述条件是满足的，即存在邻点强可区别-全染色。下面计算每一个坏事件发生的概率：

由二项式定理知，

故

第二步：构造相关图并计算相关事件数

表1 相关图R

第三步：构造常数证明以下三个不等式成立

证明(4)式只需证：

同理对于(2)式有：

同理对于(3)式有：

综上所述，取

[1] Bondy J A, Marty USR. Graph Theory with Application[M]. New York: The Macmillan Press Ltd, 1976.

[2] Burris A C, Schelp R H. Vertex-Distinguishing Proper Edge-Coloring[J]. J of Graph Theory, 1997, 26(2):73-82.

[3] Balister P N, Riordan O M, Schelp R H. Vertex‐distinguishing edge colorings of graphs[J]. Journal of graph theory, 2003, 42(2): 95-109.

[4] Zhang Z, Liu L, Wang J. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15(5): 623-626.

[5] Zhang Z, Chen X, Li J, et al. On adjacent- vertex-distinguishing total coloring of graphs[J]. Science in China Series A: Mathematics, 2005, 48(3): 289-299.

[6] 张忠辅,程辉,姚兵,等. 图的邻点强可区别全染色[J].中国科学(A辑),2007, 37(9):1073-1082.

[7] Cheng H, Wang Z. Adjacent vertex strongly distinguishing EI-total coloring of graphs[J].Shandong Univ.Nat.Sci.2010(3):289-299.

[8] 程辉,谢雁. 图的邻点强可区别VI-全染色[J].兰州大学学报:自然科学版, 2010,46(6): 97-101.

[9] 安明强. 点可区别全色数的一个上界[J].天津科技大学学报, 2009, 24(5):68-70.

[10] Michael M, Bruce R. Graph coloring and the probabilistic method[M]. New York :Springer, 2002: 1329-1356.

[11] Alon N, Spencer J H. The Probabilistic Method[M]. New York:John Wiley &Sons, 1992.

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

[13] 强会英,李沐春,张忠辅,等. 距离限制下的点可区别全色数的一个上界[J].应用数学学报,2011, 34(3):554-559.

[14] 强会英,王洪申. 图的邻点强可区别全色数的一个上界[J].数学进展, 2013, 42(6):801-805.

[15] 崔俊峰. 图的点可区别边色数的一个上界[J].首都师范大学学报:自然科学版,2017, 38(1):6-8.

AN UPPER BOUND OF THE ADJACENT-VERTEX-STRONGLY-DISTINGUISHING V-TOTAL CHROMATIC NUMBERS OF GRAPHS

*CAI Xue-peng, REN Bai-tong, FENG Miao-miao

(College of Mathematics and Physics, Xinjiang Agricultural University, Urumqi, Xinjiang 830052, China)

An upper bound for adjacent-vertex-strongly-distinguishing V-total chromatic numbers is obtained by Lovasz local lemma of probability method. We show that adjacent vertex strongly distinguishing V-total chromatic numbers of graph G is not more than 49△for△≥5, where G is a simple graph with no isolated edge and the order not less than three.

Lovasz local lemma; the adjacent-vertex-strongly-distinguishing total coloring; the adjacent-vertex-strongly-distinguishing V-total coloring

1674-8085(2018)03-0005-04

O157.5

A

10.3969/j.issn.1674-8085.2018.03.002

2018-03-09；

2018-04-16

*蔡学鹏(1991-)，男，甘肃武威人，助教，硕士，主要从事图与网络优化研究(Email:522916724@qq.com);

任佰通(1997-)，男，重庆人，新疆农业大学数理学院本科生(Email:3212989741@qq.com);

冯苗苗(1999-)，女，重庆人，新疆农业大学数理学院本科生(Email:2955398005@qq.com).