图的强直积的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-距离色数。

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社