Abstract:

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 (x1,x2)(y1,y2)∈E(G×H) whenever ［x1y1∈E(G) and x2y2∈E(H)］　or ［x1=y1 and　 x2y2∈E(H)］ or ［x2=y2 and x1y1∈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 chromatic number of G, and denoted by χ2(G). We obtain lower and upper bounds of  the 2distance chromatic number of strong product of graphs, which is Δ(G×H)+1≤χ2(G×H)≤χ2(G)·χ2(H), also shows that the bounds are tight. For some special families of graphs such as Pm×Pn, Pm×Kn, Pm×Wn, Pm×Sn, Pm×Fn, Pm×Cn(n≡0(mod 3)or =5),their 2-distance chromatic number are obtained.

Key words: graphs； strong product of graphs； 2-distance coloring； 2-distance chromatic number