图的强直积的2-距离染色(英文)

2-distance coloring of strong product of graphs

设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-距离色数。

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 n=5）,their 2-distance chromatic number are obtained.