×Pn 的r-多彩着色∗

张春梅，史雅馨，李越锋

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

0 引言

本文所研究的图是简单有限图,E(G)和V(G)分别表示G的边集和顶点集. 在图G中,顶点vi的度数(记为d(vi))是与其关联的边数, 其中δ(G)和∆(G)表示图G中的最小和最大顶点度.

记Pk+1为长度为k的路. 若P2是一个顶点集为V(P)={u0,u1,···,uk}(若i/=j,则ui/=uj),边集为E(P)={u0u1,u0u2,u1u2,u1u3,···,uk-2uk,uk-1uk}的图,则称图P2是路的平方图. 下面我们设图G={V(G),E(G)},H={V(H),E(H)}, 则顶点集为V(G)×V(H)={(u,v)|u∈V(G),v∈V(H)},边集为E(G×H)={(ui,vj)(ux,vy)|(ui,vj)和(ux,vy)相邻,当且仅当(ui,ux)∈E(G)且(vj,vy)∈E(H)},图G和H的直积记作G×H.图G的正常顶点着色是映射c:V(G)→L,该映射具有性质:如果u,v是相邻的两个点,则c(u)和c(v)是不同的.顶点k-着色是满足|L|=k的正常顶点着色. 使G具有顶点k-着色的最小整数k称为G的色数, 用χ(G)表示. Chen 等[1]提出了如果对于每个度数至少为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)表示.

对于任意图的r-多彩着色数χr(G),Lai 等[2]得到了以下规律:

并研究了χr(G),∆(G)以及|V(G)|的关系:

关于一些直积图的着色,Deepa 等[3]对图Pm×Pn的r-多彩色数χr(Pm×Pn)进行了刻画,得到了结果:

同时,Deepa 等对图Pm×Cn的r-多彩色数χr(Pm×Cn)也进行了刻画,下面给出部分结果:

关于着色的其它结果参阅文献[4-7].基于此，本文研究了路的平方图和路的直积图的r-多彩色数, 对于任意的正整数r,我们得到了r-多彩色数的精确值.

本文用矩阵

我们根据r的不同取值分别讨论r=1,2,3,4,5,6,7,8 以及r>8 的情况.

定理1当整数n,m≥3,有χ1(×Pn)=2.

证明需要考虑两种情形:

情形1当m=3 时,则∆(×Pn)=4,由式(2),χr(G)≥min{r,∆(G)}+1,有χ1(×Pn)≥2.由于d(u1,v1)=2,设c(u1,v1)=1, 则c(u2,v2)=c(u3,v2)=2,可得c(u1,v3)=c(u2,v1)=c(u2,v3)=c(u3,v1)=c(u3,v3)=1.同理可推导出图×Pn满足着色

此着色下,每个点(ui,vj)满足|c(N(ui,vj))|= min{1,d(ui,vj)},因此χ1(×Pn)≤2,所以χ1(×Pn)=2.

情形2当m≥4 时,则∆(×Pn)≥6,由式(2),χr(G)≥min{r,∆(G)}+1,有χ1(×Pn)≥2,同情形1 类似,可推导出图×Pn满足着色

此着色下,每个点(ui,vj)满足|c(N(ui,vj))|= min{1,d(ui,vj)},因此χ1(×Pn)≤2,所以χ1(×Pn)=2.

定理2当整数n,m≥3,有χ2(×Pn)=3.

证明需要考虑两种情形:

情形1当m=3 时,则∆(×Pn)=4,由式(2),χr(G)≥min{r,∆(G)}+1,有χ2(×Pn)≥3.由于d(u1,v1)=2,设c(u1,v1)=1,则c(u2,v2)=2,c(u3,v2)=3,可得c(u1,v3)=1,c(u3,v1)=3,c(u3,v3)=3.因此我们可以得到c是图×Pn的一个如下的3-着色

此着色下,每个点(ui,vj)满足|c(N(ui,vj))|= min{2,d(ui,vj)},可推出c是图×Pn的一个(3,2)-着色,所以χ2(×Pn)≤3,因此χ2(×Pn)=3.

情形2当m≥4 时,则∆(×Pn)≥6,由式(2),χr(G)≥min{r,∆(G)}+1,有χ2(×Pn)≥3.用情形1 的方法,我们可以得到c是图×Pn的一个如下的3-着色

显然, 此着色下, 每个点(ui,vj) 满足|c(N(ui,vj))| = min{2,d(ui,vj)}, 所以c是图×Pn的(3,2)-着色, 故χ2(×Pn)≤3,因此χ2(×Pn)=3.

定理3当整数n,m≥3,有

证明需要考虑三种情形:

情形1当m=3 时,则有∆(×Pn)=4,由式(2),χr(G)≥min{r,∆(G)}+1,有χ3(×Pn)≥4.因此我们可以得到c是图×Pn的一个如下的4-着色

显然,此着色下,每个点(ui,vj)满足|c(N(ui,vj))|=min{3,d(ui,vj)},所以c是图的(4,3)-着色,所以χ3(×Pn)≤4,因此χ3(×Pn)=4.

情形2当m= 4, 则有∆(×Pn) = 6, 由式(2),χr(G) ≥min{r,∆(G)}+1, 有χ3(×Pn) ≥4. 假设χ3(×Pn)=4,则×Pn有一个(4,3)-着色,因为d(u2,v1)=3 且N(u2,v1)={(u1,v2),(u3,v2),(u4,v2)},所以(u1,v2),(u3,v2),(u4,v2)着色互不相同,又因为d(u3,v1)=3 且N(u3,v1)={(u1,v2),(u2,v2),(u4,v2)},所以(u1,v2),(u2,v2), (u4,v2)着色两两不同,而d(u1,v1)=2,那么会有N(u1,v2)={(u2,v2),(u3,v2)},所以(u2,v2), (u3,v2)着色不同,综上可知(u1,v2),(u2,v2),(u3,v2),(u4,v2)四个点着色互不相同,不妨设c(ui,v2)=i(1 ≤i≤4).因为相邻顶点不能着相同的颜色, 所以c(u2,v1) /∈{1,3,4},c(u3,v1) /∈{1,2,4},c(u2,v3) /∈{1,3,4},c(u3,v3) /∈{1,2,4},从而c(u2,v1) = 2,c(u3,v1) = 3,c(u2,v3) = 2,c(u3,v3) = 3, 而N(u1,v2) = {(u2,v1),(u3,v1),(u2,v3),(u3,v3)}.|c(N(u1,v2))|=2 与|c(N(u1,v2))|≥3 矛盾,假设不成立,因此我们至少需要五种颜色进行着色,即χ3(×Pn)≥5,因此我们可以得到c是图×Pn的一个如下5-着色显然,此着色下,每个点(ui,vj)满足|c(N(ui,vj))|≥min{3,d(ui,vj)},所以χ3(×Pn)≤5,因此χ3(×Pn)=5.

情形3m≥5时,则∆(×Pn)=8,χ3(×Pn)≥4,与情形2 类似,我们至少需要五种颜色进行着色, 即χ3(×Pn)≥5.

(i)若m=0(mod 4),可以得到图×Pn的5-着色形如

(ii)若m=1(mod 4),可以得到图×Pn的5-着色形如

(iii)若m=2(mod 4),可以得到图×Pn的5-着色形如

(iv)若m=3(mod 4),可以得到图×Pn的5-着色形如

在上述着色下,每个点(ui,vj)满足|c(N(ui,vj))|≥min{3,d(ui,vj)},所以χ3(×Pn)≤5,因此χ3(×Pn)=5.

定理4当整数n,m≥3,有χ4(×Pn)=6.

证明需要考虑三种情形:

情形1当m= 3 时, 则有∆(×Pn) = 4, 由式(2),χr(G) ≥min{r,∆(G)}+1, 有χ4(×Pn) ≥5. 因为d(u2,v2) = 4, 设c(u2,v2) = 1,c(u1,v1) = 2,c(u3,v1) = 3,c(u1,v3) = 4,c(u3,v3) = 5, 这个假设具有普适性且合理,因此我们可以得到c(u3,v2) ∈{3,5},如果c(u3,v2) = 3 或c(u3,v2) = 5,则c(u2,v1),c(u2,v3) /∈{2,3,4,5}且c(u2,v1)/=c(u2,v3).所以至少需要六种颜色进行着色,因此χ4(×Pn)≥6,我们令c(u3,v2)=3,c(u2,v1)=1,c(u1,v2)=2,则c(u2,v3)=6,c(u1,v4)/∈{2,3,5,6}.我们假设c(u1,v4)=4,则c(u3,v4)∈{1,5},c(u2,v4)∈{3,6},令c(u3,v4)=5,c(u2,v4)=6,则c(u1,v5),c(u3,v5)∈{1,2,3}且c(u1,v5)/=c(u3,v5),因此我们可以得到c是图×Pn的一个如下的6-着色

显然, 此着色下, 每个点(ui,vj) 满足|c(N(ui,vj))| = min{4,d(ui,vj)}, 所以c是图×Pn的(6,4)-着色, 所以χ4(×Pn)≤6,因此χ4(×Pn)=6.

情形2当m= 4 时, 则∆(×Pn) = 6, 由式(2),χr(G) ≥min{r,∆(G)}+1, 有χ4(×Pn) ≥5. 因为d(u1,v2)=4,设c(u1,v2)=1,c(u2,v1)=2,c(u3,v1)=3,c(u2,v3)=4,c(u3,v3)=5,这个假设具有普适性且合理,因此我们可以得到c(u4,v2) /∈{1,2,3,4,5},所以我们至少需要六种颜色进行着色,可以得到c是图×Pn的一个如下的6-着色

显然,此着色下,每个点(ui,vj)满足|c(N(ui,vj))|=min{4,d(ui,vj)},故c是图的(6,4)-着色,因此χ4(×Pn)=6.

情形3当m≥5 时,则∆(×Pn)=8,与情形2 证明类似,可以得到c是图×Pn的一个如下的6-着色

显然,此着色下,每个点(ui,vj)满足|c(N(ui,vj))|=min{4,d(ui,vj)},故c是图的(6,4)-着色,因此χ4(×Pn)=6.

定理5当整数n,m≥3,有

证明需要考虑三种情形:

情形1当m=3 时,则有∆(×Pn)=4,由式(2),χr(G)≥min{r,∆(G)}+1,有χ5(×Pn)=χ4(×Pn)=6.

情形2当m= 4 时, 则有∆(×Pn) = 6, 由式(2),χr(G) ≥min{r,∆(G)}+1, 有χ5(×Pn) ≥6, 由于d(u2,v1)=3,设c(u2,v1)=1,c(u1,v2)=2,c(u3,v2)=3,c(u4,v2)=4,这个假设具有普适性且合理,因此我们可以得到c(u3,v1)=3,c(u2,v2)=1,c(u1,v1)∈{2,4},c(u4,v1)∈{2,4}.若c(u1,v1)=2 并且c(u4,v1)=2,那么我们可以得到c(u1,v3)=4,c(u3,v3)=5,c(u4,v3)=6,c(u2,v3) /∈{1,2,3,4,5,6},因此我们至少需要七种颜色进行着色.同理,若c(u1,v1)=4 且c(u4,v1)=4,我们同样需要七种颜色.若c(u1,v1)=2 且c(u4,v1)=4,那么我们可以得到c(u2,v3)=5,c(u3,v3)=6,c(u1,v3) /∈{1,2,3,4,5,6},因此我们至少需要七种颜色进行着色,即χ5(×Pn)≥7,可以得到c是图×Pn的一个如下的7-着色

显然,此着色下,每个点(ui,vj)满足|c(N(ui,vj))|=min{5,d(ui,vj)},所以c是图的(7,5)-着色,所以χ5(×Pn)≤7.因此χ5(×Pn)=7.

情形3当m≥5,则有∆(×Pn)=6,由式(2),χr(G)≥min{r,∆(G)}+1,有χ5(×Pn)≥6,假设c(u2,v2)=1,c(u1,v1) = 2,c(u3,v2) = 3, 假设合理, 则c(u4,v1) = 2,c(u4,v2) = 2,c(u3,v1) = 3,c(u1,v2) = 4,c(u2,v1) = 1,c(u2,v3) = 5,c(u3,v3) = 6. 由于d(u2,v2) = 6, 所以c(u1,v3) /=c(u4,v3),c(u4,v3) ∈{4,5}. 假设c(u1,v3) = 4,c(u4,v3) = 5, 则c(u2,v4) = 2,c(u3,v4) = 6, 假设具有普适性, 由于d(u3,v3) = 8 且c(u5,v2) /= 5,c(u5,v4) /= 5,c(u1,v4)/=5,c(u4,v4)/=5,那么我们至少需要七种颜色进行着色.若c(u1,v3)=5,c(u4,v3)=4,则c(u2,v4)=2,c(u3,v4)=6,由于d(u3,v2)=8 且d(u4,v1)=4,那么c(u5,v2)=5,c(u5,v1)=6,所以c(u6,v3)/∈{1,2,3,4,5,6}.因此我们至少需要七种颜色进行着色,即χ5(×Pn)≥7,可以得到c是图×Pn的一个如下的7-着色

显然,此着色下,每个点(ui,vj)满足|c(N(ui,vj))|= min{5,d(ui,vj)},c是图的(7,5)-着色,所以χ5(×Pn)≤7.因此χ5(×Pn)=7.

定理6当整数n,m≥3,有

证明需要考虑三种情形:

情形1当m=3 时,则有∆(×Pn)=4,由式(1)有χ6(×Pn)=χ4(×Pn)=6.

情形2当m=4 时,则有∆(×Pn)=6,由式(1)有χ6(×Pn)≥7,由于d(u2,v2)=6,我们假设c(u2,v2)=1,c(u1,v1)=2,c(u3,v1)=3,c(u4,v1)=4,c(u1,v3)=5,c(u3,v3)=6,c(u4,v3)=7,则c(u2,v1)=1,则c(u2,v1)=1 且c(u2,v3)/∈{1,2,3,4,5,6,7},因此我们至少需要八种颜色进行着色,即χ6(×Pn)≥8,可以得到c是图×Pn的一个如下的8-着色

显然,此着色下,每个点(ui,vj)满足|c(N(ui,vj))|=min{6,d(ui,vj)},则c是图的(8,6)-着色,故χ6(×Pn)≤8.因此χ6(×Pn)=8.

情形3当m≥5 时,则有∆(×Pn)=8,χ6(×Pn)≥7,我们假设c(u1,v1)=1,c(u2,v2)=2,c(u3,v2)=3,则c(u1,v2)=1,c(u2,v1)=2,c(u3,v1)=3,c(u4,v2)=4,c(u4,v1)=4,c(u5,v2)=5,则c(u2,v3)=5,c(u3,v3)=6.由于d(u2,v2)=6,所以c(u2,v4)∈{1,4},c(u3,v4)=6,c(u1,v4)/=c(u4,v4)且有c(u1,v4),c(u4,v4)∈{2,7}.由于d(u3,v3)=8,所以c(u5,v4)=3 或c(u5,v4)=5,无论c(u5,v4)=3 或c(u5,v4)=5,我们都能得到|c(N(u3,v3))|=5.因此,我们至少需要八种颜色进行着色,即χ6(×Pn)≥8,可以得到c是图×Pn的一个如下的8-着色

显然,此着色下,每个点(ui,vj)满足|c(N(ui,vj))|=min{6,d(ui,vj)},则c是图的(8,6)-着色,所以χ6(×Pn)≤8.因此χ6(×Pn)=8.

定理7当整数n,m≥3,有

证明需要考虑三种情形:

情形1当m=3 时,有∆(×Pn)=4,由式(1)有χ7(×Pn)=χ4(×Pn)=6.

情形2当m=4 时,有∆(×Pn)=6,由式(1)有χ7(×Pn)=χ6(×Pn)=8.

情形3当m≥5 时,有∆(×Pn)=8,χ7(×Pn)≥8,由于d(u1,v2)=4,设c(u1,v2)=1,c(u2,v1)=2,c(u3,v1)=3,c(u2,v3)=4,c(u3,v3)=5,假设具有普适性且合理,因此我们可以得到c(u2,v2)∈{2,4}.若c(u2,v2)=2, 则c(u3,v3) ∈{3,5}. 若c(u3,v2) = 5, 则c(u4,v2) = 6,c(u5,v2) = 4,c(u4,v1) = 1,c(u6,v2) = 3,c(u4,v3) = 6.此时, |c(N(u3,v2))| = 4, 所以我们需要其它三种颜色来让(u3,v2) 满足7-动态色数的情况, 但是c(u1,v1) /= 3,c(u1,v3)/=3,c(u5,v1)/=3,c(u5,v3)/=3,因此我们需要7,8,9 三种颜色来满足7-动态色数的情况.若c(u3,v2)=3,则c(u4,v2)=6,c(u5,v2)=4,c(u4,v1)=1,c(u6,v2)=5,c(u4,v3)=6.同理,|c(N(u3,v2))|=4,所以我们需要其它三种颜色来让(u3,v2)满足7-动态色数的情况,但是c(u1,v1)/=5,c(u1,v3)/=5,c(u5,v1)/=5,c(u5,v3)/=5,因此我们需要7,8,9 三种颜色来满足7-动态色数的情况,同理,若c(u2,v2)=4,则c(u3,v2)∈{3,5},我们能够得到结果,因此我们至少需要九种颜色进行着色,即χ7(×Pn)≥9,可以得到c是图×Pn的一个如下的9-着色

显然,此着色下,每个点(ui,vj)满足|c(N(ui,vj))|=min{7,d(ui,vj)},则c是图的(9,7)-着色,所以χ7(×Pn)≤9.因此χ7(×Pn)=9.

定理8当整数n,m≥3,有

证明需要考虑三种情形:

情形1当m=3 时,有∆(×Pn)=4,由式(1)有χ8(×Pn)=χ4(×Pn)=6.

情形2当m=4 时,有∆(×Pn)=6,由式(1)有χ8(×Pn)=χ6(×Pn)=8.

情形3当m≥5 时, 有∆(×Pn) = 8,χ8(×Pn) ≥9, 由于d(u2,v1) = 3, 设c(u2,v1) = 1,c(u1,v2) =2,c(u3,v2) = 3,c(u4,v2) = 4, 这个假设具有普适性且合理, 因此我们可以得到c(u2,v2) = 1,c(u1,v1) ∈{2,4},c(u5,v2) = 5,c(u3,v1) = 3,c(u2,v3) = 5,c(u3,v3) = 6. 若设c(u1,v1) = 2, 则c(u4,v1) = 4,c(u1,v3) ∈{7,8},c(u4,v3)∈{7,8},c(u1,v3)/=c(u4,v3).若c(u1,v3)=7 且c(u4,v3)=8,则c(u3,v4)=6,c(u2,v4)=9,c(u1,v4)={7,8},无论c(u1,v4)=7 或c(u1,v4)=8,我们都能得到c(u5,v4)=10.同理,假设c(u1,v1)=4,则c(u4,v1)=2,我们使用相同的推断方法可以得到一致的结论,即c(u5,v4)=10.因此我们至少需要十种颜色进行着色,即χ8(×Pn)≥10,可以得到c是图×Pn的一个如下的10-着色

显然,此着色下,每个点(ui,vj)满足|c(N(ui,vj))|=min{8,d(ui,vj)},则c是图的(10,8)-着色,所以χ8(×Pn)≤10.因此χ8(×Pn)=10.

定理9当整数n,m≥3,r>8 时,有

证明由图×Pn的性质知,∆(×Pn)=8,且由式(1)得,χ8(×Pn)=χr(×Pn).

2 结论

我们解决了对于一般的正整数r,图P2×P的多彩着色数.在以后的工作中,我们可以研究包含图P的图类G与图P2的图类H(P∈G,P2∈H)的直积图G×H的多彩着色数.进一步,我们可以从图G×G2的正常着色数入手,研究χ2(G×G2)和χ3(G×G2)的值以及对于一般的正整数r(r≥3),χr(G×G2)的值.