正则图点可区别全色数的一个上界

强会英, 王洪申

(1. 兰州交通大学数理学院, 甘肃 兰州　730070;2. 兰州理工大学机电工程学院, 甘肃 兰州　730050)

正则图点可区别全色数的一个上界

强会英1, 王洪申2

(1. 兰州交通大学数理学院, 甘肃 兰州730070;2. 兰州理工大学机电工程学院, 甘肃 兰州730050)

摘要：图G的一个正常全染色被称作点可区别全染色，如果G中任意两个点的色集合不同，其中每个点的色集合包含该点及其关联边的色. 应用概率的方法得到了n个点的k-正则图G的一个点可区别全色数的较小上界.

关键词：点可区别全染色; 点可区别全色数; k-正则图; Lovász局部引理

0引言

1) 对∀uv, vw∈E(G), u≠w, 有f (uv)≠f (vw).

2) 对∀uv∈E(G), u≠w, 有f (u)≠f (v), f (u)≠f (uv), f (v)≠f (uv), 则称 f 为G的一个k-正常全染色. 如果 f 是G的一个k-正常全染色，并且满足:

引理1[4]设图G(V, E)是一个简单图，如果G的最大度为Δ，则χat(G)≤2Δ+1.

猜想1[4]设G(V, E)是一个简单图, 则有χat(G)≤Δ+3.

1主要结果

定理1对n个点的k-正则图G(V, E), n≥k+2, (k≥2), 若邻点可区别全色数χat(G)≤n, 则χvt(G)≤n+1.

A) 全染色是正常的，即没有两条相邻边或两个相邻点染同一种颜色，且任何点与其关联边不能染同色；

B) 染色是点可区别的，即任何两个点的色集合不同.

下面将应用Lovász局部引理，证明如果定义的坏事件不发生的概率为正，则给出的染色法 f 是点可区别的，证明分三步.

1) 构造坏事件并计算坏事件发生的概率. 为了满足上述条件A)、B), 构造如下坏事件：

Ⅰ) 对任意的uv=e∈E(G), 令EA为点u和v染成同色的事件;

Ⅱ) 对每对相邻边e1和e2, 令EB为边e1和e2染成同色的事件;

Ⅲ) 对每个顶点u及其关联边e=uv, 令EC为边e与某一关联点u或v染成同色的事件;

Ⅳ) 对任意两点u和v，令ED为点u和v的色集合C(u)=C(v)的事件.

如果坏事件Ⅰ) 、 Ⅱ)、 Ⅲ)、 Ⅳ)不发生是可能的，则称条件A)和B)是满足的，即G存在点可区别的全染色. 各坏事件发生的概率分别为：

2)构造相关图并计算相关事件数. 构造图H, 其结点为四种类型的所有事件，其中两个结点EX和EY相关，当且仅当X和Y包含一个公共元素. 因为每个事件EX的发生，仅依赖于X的元素，所以H是上述事件的相关图.

各事件之间的具体相关数见表1，其中每个事件X与其他事件的相关数，为计算方便，部分取其上界.

表1　相关事件数表

注解(此处只对部分较难的相关数加以说明)： 每个类型Ⅰ事件中包含了2个点 u 与 v ，与u同色集的点至多有n-1个，与v同色集的点至多有n-2个，故Ⅰ与Ⅳ事件的相关数至多为 2n-3； 当类型Ⅳ事件与类型Ⅰ事件含有一个公共点 v 时，与相邻的点至多有 k 个，与某一点 u 相邻的点至多为 k 个，故Ⅳ事件与Ⅰ事件相关数至多为 2k； 当类型Ⅳ事件与类型Ⅱ事件含有一个公共点 u 时，与点 u 相邻的边至多为k条，与任意一条边相邻的边数为k-1条，故Ⅳ与Ⅱ事件的相关数至多为2 k(k-1)个； 类型Ⅳ事件中包含了2个点，与任一点 u 同色集的点至多为n-1个，与点 v 同色集的点至多为n-1个，故Ⅳ事件与Ⅳ事件的相关数至多为2n-2，其他相关数算法与此类似.

为此，只需证明以下四个不等式成立：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

比较不等式(5)、 (6)、 (7)、 (8)，如果n, k满足一定条件时，式(8)成立，则式(5)、 (6)、 (7)都成立，所以只需证明不等式(8).

要使不等式(8)成立，即25n2≥8k2+16n+32k-16都成立，讨论该式可知，在满足条件n≥4, k≥2(n≥k+2)时，不等式(8)成立，从而不等式(1)、 (2)、 (3)、 (4)都成立.

综上可见，当n≥4, k≥2(n≥k+2)时，对n个点的k-正则图G(V, E), 若邻点可区别全色数χat(G)≤n, 则χvt(G)≤n+1成立.

参考文献：

[1] ZHANG Z F, LIU L Z, WANG J F. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15: 623-626.

[2] BALISTER P N, RIORDAN O M, SCHEIP R H. Vertex-distinguishing edge colouings of grapgs[J]. J of Graph Theory, 2003, 42: 95-109.

[3] 张忠辅，李敬文，陈祥恩, 等. 图的距离不超过β的任意两点可区别的边染色[J].数学学报，2006，49(3): 703-708.

[4] ZHANG Z F, CHEN X E, LI J W. On the adjacent vertex distinguishing total coloring of graphs[J]. Sci China Ser A, 2005, 48(3): 289-299.

[5] ZHANG Z F, QIU P X, XU B G,etal. Vertex-distinguishing total coloring of graphs[J]. Ars Comb, 2008 (87): 33-45.

[6] 张忠辅，李敬文，陈祥恩, 等. 图的距离不大于β的点可区别的全染色[J].中国科学(A辑)，2006，36(10): 1 119- 1130.

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

[8] ALON N, SPENCER J H. The probabilistic method[M]. New York: Wiley, 1992.

(责任编辑： 沈芸)

The bound of vertex-distinguishing total chromatic number of regular graphs

QIANG Huiying1, WANG Hongshen2

(1. School of Mathematics and Physics, Lanzhou Jiaotong University，Lanzhou，Gansu 730070, China;2. School of Technology Engineering, Lanzhou University of Technology, Lanzhou，Gansu 730050, China)

Abstract:A proper total coloring of the graph G is called vertex distinguishing total coloring, if any two vertices have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it. In this paper, we obtained the new upper bound of vertex distinguishing total chromatic number of the k-regular graphs with n order by the way of probability.

Keywords:ertex distinguishing total coloring; vertex distinguishing total chromatic number; k-regular graphs; Lovász local lemma

DOI:10.7631/issn.1000-2243.2016.03.0311

文章编号：1000-2243(2016)03-0311-04

收稿日期:2014-04-29

通讯作者:强会英(1968-)，教授，主要从事图论及其应用研究，qhy2005ww@126.com

基金项目：国家自然科学基金资助项目(6126045); 甘肃省自然科学基金资助项目(1208RJZA281); 甘肃省制造信息化工程技术研究中心开放基金资助项目(2012MIE01F01); 甘肃省高校基本科研业务费(2014GSF1015A)

中图分类号：O157.5

文献标识码：A