圈与路的笛卡尔乘积图的多彩染色

张春梅, 史雅馨, 杜伊诺

(新疆大学数学与系统科学学院，乌鲁木齐 830017)

0 引言

图论起源于1736 年，欧拉向圣彼得堡科学院递交的论文《哥尼斯堡的七座桥》解答了七桥问题，并开创了数学一个新的分支—图论与几何拓扑。图论中的四色问题已经成为了近代三大数学难题之一，人类在寻找四色问题的答案的同时，推动了图论的发展，尤其是对图的染色理论、平面图理论、代数拓扑等分支的发展起到了重要的推动作用。随着图论的发展，图论理论逐渐成为离散数学中的重要知识之一。随着图论的发展更是被广泛应用于社会生活的各个方面，比如交通规划、经济分析、网络通信等。圈和路是图论研究中的重要对象，在图论中占有非常重要的地位，其实际应用也越来越广泛。高速数字计算机的发明，促使更多数学家对“四色问题”的研究。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976 年6 月，美国数学家Appel 和Haken 与运用计算机的专家Kock 三人合作，在美国伊利诺斯大学两台不同的电子计算机上，用了1 200 个小时，作了100 亿个判断，结果没有一张地图是需要五色的，最终证明了四色定理[1]，轰动了世界。在日常生活中，很多优化问题和网络问题，诸如计算机网络中的文件传输问题、时间表问题、信号发射问题等都涉及到图的圈和路理论。本文主要对圈与路的笛卡尔积图的多彩染色进行研究。

图的r-多彩染色的另一个研究动机源于电力网络最优重新配置中多代理系统部署中的通信问题[2–5]。代理是一种能够在该环境中自主行动以实现其设计目标的计算机系统。自治意味着环境功能中的组件完全受自己的控制。近年来，结合图算法在电力网络优化重构中使用多智能体系统已得到了广泛应用。在电力网络最优重构过程中部署的多智能体系统的图建模中，形成图模型来模拟智能体的通信和工作关系，其中智能体被建模为顶点，并且如果对应的智能体在两个顶点相邻工作中需要沟通。为了执行最佳的重新配置，每个智能体需要从其相邻智能体传感器获取特定但不同种类的信息，并使用这些信息做出自己的决策并采取行动。在建模中，代理以无线方式进行通信。每个代理可以接收不同频率的信号，但只能有一个发射频率。要求相邻智能体必须具有不同的发射频率，并且对于固定整数r> 0，每个智能体需要从其相邻智能体接收至少r种不同的信息，这些信息通过其发射频率来区分。这相当于要求每个代理必须至少使用r个不同发射频率的邻居。为了将发射频率分配给代理，很自然地将其视为图的r色调染色问题，其中发射频率是颜色。

本文所研究的图是简单有限图，E(G)和V(G)分别表示图G的边集和顶点集。在图G中，顶点vi的度数(记为d(vi))是与其关联的边数，其中δ(G)和∆(G)表示图G中的最小和最大顶点度。记Pn为长度为n-1 的路，Cm为长度m个点的圈。图G和H的笛卡尔乘积图记为G□H，其顶点集为V(G)×V(H)，(u1,v1)与(u2,v2)相邻当且仅当u1=u2,v1v2∈E(H)，或v1=v2,u1u2∈E(G)。图G的正常顶点染色是映射c:V(G)→L，该映射具有性质：如果u和v是相邻的两个点，则c(u)和c(v)是不同的。顶点k-染色是满足|L| =k的正常顶点染色。使G具有顶点k-染色的最小整数k称为G的色数，并用χ(G)表示。2001 年，Montgomery[6]首次提出了r-多彩染色的定义，并提出了如果对于每个度数至少为2 的顶点v和v的邻点至少接收两种不同的颜色，则一个正常的顶点k-染色称为2-动态染色。使G具有2-动态染色的最小正整数k称为图G的2-动态色数，并用χ2(G)表示。此外，2-动态染色也被称为动态染色。通常，如果对于度数至少为r的每个顶点v的邻点至少接收r种不同的颜色，则正常的顶点k-染色称为(k,r)-染色。使G具有(k,r)-染色的最小正整数k称为G的r-多彩色数，并用χr(G)表示。

Lai 等人[7]证明了当n ≥3,r ≥2 时，n个顶点的圈Cn的多彩色数为

Lai 等人[8]证明了当G是一个连通图时，有以下结论：

1) 如果G ̸=C5, ∆(G)≤3，则χ2(G)≤4；

2) 如果∆(G)≥4，则χ2(G)≤∆(G)+1。Akbari 等人[9]证明了对于自然数m和n(m,n ≥2)，有以下结论：

1) 如果m,n ≥2，则χ2(Pm□Pn)=4；

2) 如果m ≥3，则

Kang 等人[11]证明了对于自然数m和n(m,n ≥2)，有以下结论：如果mn ≡2(mod 4)，则χ3(Pm□Pn)=5。Suil[13]证明了对于自然数m,n ≥3，有以下结论：

1) 对于m ≤n(mod 4)，有

Lai 等人在文献[7]中给出了χr(G)、∆(G)以及|V(G)|的如下关系

在上述工作基础上，本文研究圈和路的笛卡尔乘积图的r-多彩色数。

1 图Cm□Pn 的多彩色数

在本节中，我们一般将笛卡尔乘积图G的染色表示为矩阵A，并定义c(ui,vj) =aij,A=[aij]m×n。

对于自然数m(m ≥3)和n(n ≥2)，V(Cm) ={u1,u2,···,um},V(Pm) ={v1,v2,···,vn}。Cm和Pn的笛卡尔乘积图记为图G，用G=Cm□Pn表示，其中V(G) ={(ui,vj)|ui ∈V(Cm),vj ∈V(Pn)}。

本文根据正整数m和n的取值不同，分类讨论Cm□Pn的r-hued 色数。由于r=4 的证明过于繁琐，在此不一一列出，只给出r=3 的情况的证明。当r=3 时，有如下结论。

定理1 对于任意两个自然数m(m ≥3)和n(n ≥2)，有

证明 设V(Cm)={u1,u2,···,um},V(Pn)={v1,v2,···,vn}，并且G=Cm□Pn。由(1)式可知，χr(G)≥min{∆(G),r}+1，故χ3(Cm□Pn)≥4。我们分以下三种情形进行讨论。

情形1m ≡0(mod 4)。

当4|m时，给出一个(4,3)-染色

矩阵A从第3 列开始循环

因为对于任意一条边uivj ∈E(Cm□Pn)，我有c(ui)̸=c(vj)，所以按照Am×n的染色c是一个(4,1)-染色。下面证明c是一个(4,3)-染色：

i) 任选一个点(ui,vk)∈V(Cm□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NCm□Pn(ui,vk))|=3；

ii) 任选一个点(ui,vk)(i ̸={1,n})，并且d(ui,vk)=4，我们有|c(NCm□Pn(ui,vk))|=3；

故按照Am×n这样染色，是一个(4,3)-染色，所以χ3(Cm□Pn)≤4。由(1)式可知χr(G)≥min{∆(G),r}+1，故χ3(Cm□Pn)≥4。因此，χ3(Cm□Pn)=4。

情形2m=3 或m=6 且n=2k(k ≥1)或m ∈{7,11}且n ̸=3k+1(k ≥1)，我们又可分以下四种情况进行讨论。

情形2.1m=3，给出一个(6,3)-染色c，按照A3×n进行染色

矩阵A从第3 列开始循环

因为对于任意一条边uivj ∈E(C3□Pn)，我们有c(ui)̸=c(vj)，所以按照A3×n的染色c是一个(6,1)-染色。下面证明c是一个(6,3)-染色：

i) 任选一个点(ui,vk)∈V(C3□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC3□Pn(ui,vk))|=3；

ii) 任选一个点(ui,vk)(i ̸={1,n})，并且d(ui,vk)=4，我们有|c(NC3□Pn(ui,vk))|=3；

故按照A3×n这样染色，是一个(6,3)-染色，所以χ3(C3□Pn)≤6。

接下来，用反证法证明χ3(C3□Pn)≥6。假设χ3(C3□Pn)≤5，对于第1 列和第2 列来说，因为点(u1,v1)、(u2,v1)和(u2,v1)在一个三角形中，我们不妨设c(u1,v1) = 1,c(u2,v1) = 2,c(u3,v1) = 3。为了满足点(u1,v1)和(u2,v1)的多彩染色的条件，只能c(u1,v2) = 4,c(u2,v2) = 5，那么c(u3,v2)∈{1,2,3,4,5}，这与(5,3)-染色的条件相矛盾，所以χ3(C3□Pn)≥6，故m=3 时，χ3(C3□Pn)=6。

情形2.2m=6 且n=2k(k ≥1)，给出一个(6,3)-染色

矩阵A从第3 列开始循环

因为对于任意一条边uivj ∈E(C6□Pn)，我们有c(ui)̸=c(vj)，所以按照A6×n的染色c是一个(6,1)-染色。下面证明c是一个(6,3)-染色：

i) 任选一个点(ui,vk)∈V(C6□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC6□Pn(ui,vk))|=3；

ii) 任选一个点(ui,vk)(i ̸={1,n})，并且d(ui,vk)=4，我们有|c(NC6□Pn(ui,vk))|=3；

故按照A6×n这样染色，是一个(6,3)-染色，所以χ3(C6□Pn)≤6。

接下来，用反证法证明χ3(C6□Pn)≥6。假设χ3(C6□Pn)≤5，对于第n-1 列和第n列来说，我们先对第n-1 列点进行染色，进行如下讨论：

i) 如果第n-1 列按123123 的顺序来染，那么第n列只能染454545，第n列的点不符合多彩染色的条件，故矛盾；

ii) 如果第n-1 列按123423 的顺序来染，那么第二列只能染454，第2 列染5 的点不符合多彩染色的条件，故矛盾；

iii) 如果第n- 1 列按123453 的顺序来染，无论怎样进行染色，第2 列都会出现aba(a,b ∈{1,2,3,4,5})的片段，不符合多彩染色的条件，故矛盾；因此c(u3,v2)不满足(5,3)-染色的条件，故χ3(C6□Pn)≥6。

综上，得m=6 且n=2k(k ≥1)时，χ3(C6□Pn)=6。

情形2.3 当m=7,n ̸=3k+1(k ≥1)时，给出一个(6,3)-染色

矩阵A从第3 列开始循环

因为对于任意一条边uivj ∈E(C7□Pn)，我们有c(ui)̸=c(vj)，所以按照A7×n的染色c是一个(6,1)-染色。下面证明c是一个(6,3)-染色：

i) 任选一个点(ui,vk)∈V(Cm□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC7□Pn(ui,vk))|=3；

ii) 任选一个点(ui,vk)(i ̸={1,n})，并且d(ui,vk)=4，我们有|c(NC7□Pn(ui,vk))|=3；

故按照A7×n这样染色，是一个(6,3)-染色，所以χ3(C7□Pn)≤6。

接下来，用反证法证明χ3(C7□Pn)≥6。假设χ3(C7□Pn)≤5，对于任意两列来说，如果依次设c(u1,vk) = 1,c(u2,vk) = 2,c(u7,vk) = 3,c(u1,vk+1) = 4，按照这种方式染色，第k列按最小染色数染色的染色方式为αTk= (1,2,4,3,1,2,3)。由多彩染色定义可知，第k+1 列染色情况为

由多彩染色的定义可知，c(u7,vk+1)=5,c(u7,vk+1)满足染色。第k+2 列染色情况为

且可知

因此c(u7,vk+2)不满足(5,3)-染色的条件，χ3(C7□Pn)≥6，故m= 7,n ̸= 3k+1(k ≥1)时，χ3(C7□Pn)=6。

情形2.4 当m=11 且n ̸=3k+1(k ≥1)时，给出一个(6,3)-染色

矩阵A从第3 列开始循环

因为对于任意一条边uivj ∈E(C11□Pn)(n ̸=3k+1,k ≥1)，我们有c(ui)̸=c(vj)，所以按照A11×n的染色c是一个(6,1)-染色。下面证明c是一个(6,3)-染色：

i) 任选一个点(ui,vk)∈V(C11□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC11□Pn(ui,vk))|=3；

ii) 任选一个点(ui,vk)(i ̸={1,n})，并且d(ui,vk)=4，我们有|c(NC11□Pn(ui,vk))|=3；

故按照A11×n这样染色，是一个(6,3)-染色，所以χ3(C11□Pn)≤6。

接下来，用反证法证明χ3(C11□Pn)≥6。假设χ3(C11□Pn)≤5，对于任意两列来说，如果依次设c(u1,vk) = 1,c(u2,vk) = 2,c(u11,vk) = 3,c(u1,vk+1) = 4，按这种方式进行染色，第k列按最小染色数染色的方式为αTk= (1,2,4,3,1,2,4,3,1,2,3)。由多彩染色的定义可知，第k+1 列的情况为

因此c(u11,vk+2)不满足(5,3)-染色的条件，故m=11 且n ̸=3k+1(k ≥1)时，χ3(C11□Pn)=6。

情形3 i) 4 łm且m ̸={3,6,7,11}。

ii)m=6 且n=2k(k ≥1)。

iii)m ∈{7,11}且n=3k+1(k ≥1)。

我们分以下三种情况讨论。

情形3.1m ≡1(mod 4)给出一个(5,3)-染色因为对于任意一条边uivj ∈E(Cm□Pn)，我们有c(ui)̸=c(vj)，所以按照Am×n的染色c是一个(5,1)-染色。下面证明c是一个(5,3)-染色：

i) 任选一个点(ui,vk)∈V(Cm□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NCm□Pn(ui,vk))|=3；

ii) 任选一个点(ui,vk)(i ̸={1,n})，并且d(ui,vk) = 4，我们有|c(NCm□Pn(ui,vk))|=3；

故按照Am×n这样染色，是一个(5,3)-染色，所以χ3(Cm□Pn)≤5。

接下来，用反证法证明χ3(Cm□Pn)≥5。假设χ3(Cm□Pn)≤4，对于第1 列和第2 列来说，假设依次设c(u1,v1) = 1,c(u2,v1) = 2,c(u3,v1) = 3,c(u4,v1) =4,c(u5,v1) = 3，按这种方式染色，由多彩染色定义可知，第2 列染色肯定会出现44 的染色片段，这与正常染色的条件矛盾。因此c不满足(4,3)-染色的条件，故m ≡1(mod 4)时，χ3(Cm□Pn)=5。

情形3.2m ≡2(mod 4)，可分为以下两种情形。

情形3.2.1m ≡2(mod 4)且m ̸=6 时，给出一个(5,3)-染色

因为对于任意一条边uivj ∈E(Cm□Pn)，我们有c(ui)̸=c(vj)，所以按照Am×n的染色c是一个(6,1)-染色。下面证明c是一个(6,3)-染色：

i) 任选一个点(ui,vk)∈V(Cm□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NCm□Pn(ui,vk))|=3；

ii) 任选一个点(ui,vk)(i ̸={1,n})，并且d(ui,vk) = 4，我们有|c(NCm□Pn(ui,vk))|=3；

故按照Am×n这样染色，是一个(6,3)-染色，所以χ3(Cm□Pn)≤6。

接下来，用反证法证明χ3(Cm□Pn)≥5。假设χ3(Cm□Pn)≤4，取第1 列和第2 列两列，对于第1 列：

i) 如果我们按照121234···1234 的序列来染色，为了满足第1 列的点的多彩染色的条件，那么在第2 列肯定会出现44 的染色片段，这与正常染色的条件矛盾；

ii) 如果我们按照12341234··· 的序列来染色，要么在第1 列出现aba(ab ∈{1234})的染色片段，要么在第2 列出现44···44 的染色片段，这与多彩染色的条件矛盾；故m ≡2(mod 4)且m ̸=6 时，χ3(Cn□Pm)=5。

情形3.2.2 当m=6 且n=2k+1(k ≥1)时，取

矩阵A6×n={α1,α2,···,αn}满足

因为对于任意一条边uivj ∈E(C6□Pn)，我们有c(ui)̸=c(vj)，所以按照A6×n的染色c是一个(5,1)-染色。下面证明c是一个(5,3)-染色：

i) 任选一个点(ui,vk)∈V(C6□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC6□Pn(ui,vk))|=3；

ii) 任选一个点(ui,vk)(i ̸={1,n})，并且d(ui,vk) = 4，我们有|c(NC6□Pn(ui,vk))|=3；

故按照A6×n这样染色，是一个(5,3)-染色，所以χ3(C6□Pn)≤5。

接下来，用反证法证明χ3(C6□Pn)≥5。假设χ3(C6□Pn)≤4，取第1 列和第2 列两列，我们进行如下讨论：

i) 如果第1 列，我们按照123123 来染色，为了满足第1 列的点的多彩染色的条件，那么在第2 列肯定会出现44 的染色片段，这与正常染色的条件矛盾；

ii) 如果第1 列，我们按照123423 来染色，为了满足第1 列的点的多彩染色的条件，那么在第2 列也会出现44 的染色片段，这与正常染色的条件矛盾；故m=6 且n=2k+1(k ≥1)时，χ3(C6□Pn)=5。

情形3.3m ≡3(mod 4)且m/∈{3,7,11}或m={7,11}且n= 3k+1(k ≥1)。给出一个(5,3)-染色。

情形3.3.1 当m ≡3(mod 4)且m/∈{3,7,11}时，令

因为对于任意一条边uivj ∈E(Cm□Pn)，我们有c(ui)̸=c(vj)，所以按照Am×n的染色c是一个(5,1)-染色。下面证明c是一个(5,3)-染色：

i) 任选一个点(ui,vk)∈V(Cm□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NCm□Pn(ui,vk))|=3；

ii) 任选一个点(ui,vk)(i ̸={1,n})，并且d(ui,vk) = 4，我们有|c(NCm□Pn(ui,vk))|=3；

故按照Am×n这样染色，是一个(5,3)-染色，所以χ3(Cm□Pn)≤5。

接下来，用反证法证明χ3(Cm□Pn)≥5。假设χ3(Cm□Pn)≤4，对于第1 列和第2 列来说，如果第1 列按照序列1231234···1234 来进行染色，那么在第2 列上肯定会出现44 的染色片段。这与正常染色的条件相矛盾，因此c不满足(4,3)-染色的条件，χ3(Cm□Pn)≥5，故m ≡3(mod 4)且m/∈{7,11}时，χ3(Cm□Pn)=5。

情形3.3.2 当m=7,n=3k+1(k ≥1)时，令

矩阵A7×n={α1,α2,···,αn}满足

因为对于任意一条边uivj ∈E(C7□Pn)，我们有c(ui)̸=c(vj)，所以按照A7×n的染色c是一个(5,1)-染色。下面证明c是一个(5,3)-染色：

i) 任选一个点(ui,vk)∈V(C7□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC7□Pn(ui,vk))|=3；

ii) 任选一个点(ui,vk)(i ̸={1,n})，并且d(ui,vk) = 4，我们有|c(NC7□Pn(ui,vk))|=3；

故按照A7×n这样染色，是一个(5,3)-染色，所以χ3(C7□Pn)≤5。

接下来，用反证法证明χ3(C7□Pm)≥5。假设χ3(C7□Pm)≤4，取第1 列和第2 列两列，我们进行如下讨论：如果第1 列按照1234123 来染色，为了满足第1 列的点的多彩染色的条件，那么在第2 列肯定会出现44 的染色片段，这与正常染色的条件矛盾，故m= 7,n= 3k+1(k ≥1)时，χ3(C7□Pm)≥5。因此，当m= 7,n= 3k+1(k ≥1)时，χ3(C7□Pm)=5。

情形3.3.3 当m=11,n=3k+1(k ≥1)时，令因为对于任意一条边uivj ∈E(C11□Pn)，我们有c(ui)̸=c(vj)，所以按照A11×n的染色c是一个(5,1)-染色。下面证明c是一个(5,3)-染色：

i) 任选一个点(ui,vk)∈V(C11□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC11□Pn(ui,vk))|=3；

ii) 任选一个点(ui,vk)(i ̸={1,n})，并且d(ui,vk)=4，我们有|c(NC11□Pn(ui,vk))|=3；

故按照A11×n这样染色，是一个(5,3)-染色，所以χ3(C11□Pn)≤5。

接下来，用反证法证明χ3(C11□Pm)≥5。假设χ3(C11□Pm)≤4，取第1 列和第2 列两列，我们进行如下讨论：如果第1 列，我们按照12341234123 来染色，为了满足第1 列的点的多彩染色的条件，那么在第2 列肯定会出现44 的染色片段，这与正常染色的条件矛盾，故m=11,n=3k+1(k ≥1)时，χ(C11□Pm)≥5。

综上，4 łm且m ̸={3,6,7,11}；m= 6 且n= 2k(k ≥1)；m ∈{7,11}且n=3k+1(k ≥1)满足χ3(Cm□Pn)=5。

2 结论

已有文献中证明了圈与路的笛卡尔乘积图Cm□Pn的2-多彩染色数，我们研究了圈与路的笛卡尔乘积图Cm□Pn的r-多彩染色数(r ∈{3,4})，本文只给出了圈与路的笛卡尔乘积图Cm□Pn的3-多彩染色数的证明。对于r= 4 的情况，其证明方法与r= 3 时的证明方法完全相同，证明过程过于繁琐，本文没有一一列出。

在以后的工作中，我们可以研究任意两个图做笛卡尔乘积图的正常染色数，进而研究其多彩染色数。本文的研究对于研究电力网络的最优重新配置中多代理系统的通讯问题具有一定的指导意义。