路的积图的3- 距离染色

代青昂毛

（ 西北民族大学数学与计算机科学学院，甘肃 兰州730030）

1 概述

图的距离染色是由F. Kramer 与H. Kramer 于1969 年首次在文献[1]中提出的，后来在文献[2]中被表述为k- 距离染色。所谓图的k- 距离染色是指图中距离不超过k 的顶点染不同颜色的点染色，其中k 为正整数. 为了研究图G的k- 距离染色数，Kramer 等人在文献[3]中定义了图G 的k- 方图，得到了图G 的k- 方图距离色数与k- 距离色数相等的结论。关于图的积图的距离染色，Kim 在文献[4] 中研究m阶路Pm与n 阶圈Cn 的直积Pm×Cn的2- 距离染色，证明了Pm×Cn的2- 距离染色数等于5 或6。Kim在文献[5]中研究了圈的笛卡尔积的2- 距离染色。Fertin 等在文献[6]中得到了路的笛卡尔积的k- 距离色数。

本文研究路的半强积与强积的3- 距离染色。图的半强积与强积的定义具体如下：

定义1.1[7]设有G 和H 两个简单图，图G 和H 的半强积G·H有顶点集V（G·H）=V（G）×V（H），任意两个顶点（u1，v1）与（u2，v2）相邻当且仅当u1u2∈E（G）且v1v2∈E（H），或者u1=u2且v1v2∈E（H）。

在后文中要用到以下引理：

引理1.1[2]对图G的任意子图H，有χk（H）≤χk（G）。

2 主要结论及其证明

设Pm=u0u1…um-1与Pn=v0v1…vn-1分别为m≥2 阶和n≥2 阶路。为了方便在直角坐标系中研究，把顶点（uy，vx）记为（x，y），其中x=0，1，…，n-1，y=0，1，…，m-1。记（x）k=x（mod k），其中x为整数。

关于路的半强积的3- 距离染色，有以下定理2.1- 定理2.3。

定理2.1 对任意的整数n≥4，有χ3（P2·Pn）=8。

证明P2·P4中任意两点之间的距离不超过3，并且顶点数等于8，所以χ3（P2·Pn）=8。由于P2·P4包含于P2·Pn，根据引理1.1 可知，χ3（P2·Pn）≥8。为证明χ3（P2·Pn）≤8，仅需用8 种颜色构造一个P2·Pn的3- 距离染色。对x=0，1，…，n-1，y=0，1，令σ（x，y）=（x+2y）8。显然，σ 所用颜色集为{0，1，2，…，7}。

现在证明σ 是P2·Pn的3- 距离染色。在P2·Pm中取任意顶点u=（x，y），那么与之任意距离不超过3 的顶点可能为v（x，y，）=（x±а，y±1），其中а∈{1，2，3}，y，y，∈{0，1}。根据σ 的定义，有σ（v）=（x±а+2（y±1））8。假设σ（u）=σ（v），则（x+2y）8=（x±а+2y±2）8，即（±а±2）8=0，这与0≤|±а±2|≤5 矛盾。因此，σ（u）≠σ（v），即σ 是P2·Pn的一个3- 距离染色。……