图的强直积的2-距离染色

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。

2-distance coloring of strong product of graphs

Let G,H be simple graphs of order at least 2. The strong product of graph G and H is the graph G(□)H with vertex set V(G) ×V(H), and (x_1 ,x_2) (y_1 ,y_2)∈ E(G(□)H) whenever [x_1,y_1 ∈ E(G) and x_2y_2∈E(H)] or [x_1=Y_1 and x_2y_2 ∈ E(H)] or [x_2 = y_2 and x_1y_1 ∈ E(G)]. A 2-distance coloring using k colors of a graph G is a mapping f from V(G) to {1,2, ... ,k} such that two distinct vertices lying at a distance less than or equal to 2 must be assigned different colors. The minimum number of colors required for a 2-distance coloring of G is called the 2-distance chromat ic number of G, and denoted by X_2 (G). We obtain lower and upper bounds of the 2-distance chromatic number of strong product of graphs, which is △(G(□)H) + 1≤x_2 (G(□)H)≤x_2(G)·x_2 (H), also shows that the bounds are tight. For some special families of graphs such as P_m(□P_n,P_m(□)K_n, P_m(□)W_n, P_m(□)S_n, P_m(□)F_n, P_m(□)C_n(n=0(mod 3) or n = 5), their 2-distance chromatic number are obtained.