(P^2)_n和(P^3)_n的D(3)-点可区别全染色

D(3)-Vertex-Distinguishing Total Coloring of (P^2)_n and (P^3)_n

图的染色问题是图论研究的经典领域,在网络结构和实际生活中都有着广泛的应用,随着计算机和通讯、电力网络的日益发展,染色问题成为近年来图论研究的热点.图的D(β)-点可区别全染色又是染色问题中的难点.通过分类讨论、归纳探究,在图的点边集合与色集合间构造了一种一一对应关系.讨论了幂图Pkn(k=2,3)的点可区别全染色,使得距离不大于3(D(3))的任意2点都有不同的色集合,得到幂图Pkn(k=2,3)的D(3)-点可区别全染色数.

The coloring problem of graph is the classical field of graph theory which is widely used in the network structure and practical life. With the development of the computer, communication and power grid, the coloring problem is becoming a hot topic in recent years. The D（β）-vertex-distinguishing total coloring is a difficult point of the coloring problem. Through classification and inductive exploration, we set up a one to one correspondence be- tween the set of vertices and edges and the set of color. In this paper, the vertex distinguishing total coloring of P2n and P3n is discussed, so that every two vertices with distance no more than three have different set of colors. At the same time, we obtain the D （3） -vertex distinguishing total chromatic number of P2n and P3n.