弱直积图的2-距离色数

2-distance chromatic number of weak direct product graphs

图G(V,E)的2-距离染色是指正常的顶点染色,且任意距离不大于2的两个顶点着不同的颜色.得到弱直积图的一个2-距离色数的可达界,即Δ(G).Δ(H)+1≤χ2(G×H)≤χ2(G).2χ(H),且给出一些特殊弱直积图的2-距离色数,说明此界可达.如χ2(P2×Pn)=Δ(P2).Δ(Pn)+1=3(n≥3),χ2(Pm×Pn)=Δ(Pm).Δ(Pn)+1=5(m≥3,n≥3)说明下界可达,χ2(Km×Kn)=χ2(Km).2χ(Kn)=mn,说明上界可达.

The 2-distance coloring of graph G（V,E） means a proper vertex coloring such that no two vertices at distance less than or equal to 2 in G were assigned the same color.The approachable boundary of 2-distance chromatic number of weak direct product graphs was obtained,where Δ（G）·Δ（H）＋1≤χ2（G×H）≤χ2（G）·χ2（H）, and some 2-distance chromatic numbers of particular weak direct product graphs were given,also,showing that this boundary could be reached.For example,χ2（P2×Pn）=Δ（P2）.Δ（Pn）＋1=3（n≥3）,χ2（Pm×Pn）=Δ（Pm）.Δ（Pn）＋1=5（m≥3,n≥3）implies that the lower boundary was approachable and χ2（Km×Kn）=χ2（Km）.2χ（Kn）=mn implies that the upper boundary was approachable.