UPPER BOUNDS FOR THE D(β)-VERTEX-DISTINGUISHING EI-TOTAL CHROMATIC NUMBERS OF GRAPHS

摘要：

Let G(V,E) be a simple connected graph, and |V(G)| > 2.Suppose k, β are both positive integers and f is a mapping from V(G)∪E(G) to 1, 2, ???, k, such that 1) □uv∈E (G)(u≠v), f(u)≠f(v); 2) □uv∈E(G)(u≠v), dG(u,v) ≤ β, where dG(u,v) denotes the distance between u and v, we have C(u)≠C(v), where C(u)=f(u)∪ f(uv)|uv∈E(G).Then f is called a k-D(β)-vertex-distinguishing El-total coloring of G.In this paper we study the upper bounds for the D(β)-vertexdistinguishing EI-total chromatic numbers by the probability method and prove that Xei,βvt(G) ≤ 32Δ(β+2)/Δ when Δ ≥ 5, β ≥ 4.

关键词： D(β)-vertex-distinguishing total coloring D(β)-vertex-distinguishing EI-total coloring D(β)-vertex-distinguishing EI-total chromatic number Lovasz Local Lemma

作者: XINSHENG LIU ZHIQIANG WANG

作者单位: College of Mathematics and Information Science,Northwest Normal University,Lanzhou,Gansu 730070,China

会议类型: 国际会议

会议名称: 2011 3rd International Conference on Computer Technology and Development(2011第三届计算机技术与发展国际会议 ICCTD2011)

会议地点: 成都

会议语种:英文

页码: 1080-1084

在线出版日期: 2011-11-25（万方平台首次上网日期，不代表论文的发表时间）