Pm和Pn的强直积的强边染色

谭亚茹，马登举

（南通大学理学院，江苏 南通 226019）

设V（G）、E（G）分别表示图G的顶点集和边集.图 G 的 k-边正常染色是指映射 f：E（G）→{1，2，…，k}，使得对图G中任意相邻的边e1、e2，均有.设e1、e2是图G的2条不相邻的边，e1的一个端点到e2的一个端点且不经过e1和e2的路称为e1到e2的一条路，其中最短的一条路所含的边数称为e1到e2的距离.图G的强边染色是图G的一个正常边染色，满足任意2条距离小于或等于1的边染色不相同.在图G的所有强边染色中，使用颜色最少的强边染色所含颜色的数目称为G的强边色数，记为χS′（G）.1985年，Erdos和Nestil提出猜想[1]：当一个图的最大度Δ分别为偶数和奇数时，其强边色数分别不超过5Δ2/4和（5Δ2-2Δ+1）/4.之后相关学者对强边染色进行了研究.文献[2-3]研究了围长不小于6的平面图的强边染色，得到这类图强边色数的上界；文献[4]给出了2个图笛卡尔积和强积的强边色数的上界或下界；还有一些文献[5-7]对一些特殊图给出了其强边色数的确切值.

令G1、G2是阶至少为2的简单图.图G1与G2的强直积G1G2是这样的一个图，其顶点集合为V（G1G2）=V（G1）× V（G2），边集合为

文献[4]证明了对于简单图G1和G2的强直积G1G2，有

这里χ（H）表示H的色数.

设F是一个至少有2个顶点的路.因F是一个二部图，故F的色数为2.不难发现F的强边色数至多为3.设Pl表示有l个顶点的路.当m≥2，n≥2时，由式（1）有χS′（PmPn）≤30.本文得到如下结果：当m=2，n≥3时，χS′（PmPn）=14；当m=3，n≥3时，χS′（PmPn）=20；当m≥4，n≥4时，χS′（PmPn）=26.

定理1当n≥3时，χS′（P2Pn）=14.

证明先证明 χS′（P2Pn）≥14.设 H1是一个有8个顶点的图，如图1所示.显然H1中任意2条边之间的距离都不大于1.而图H1含有14条边，所以χS′（H1）≥14.因为图P2Pn有一个子图同构于图H1，所以χS′（P2Pn）≥χS′（H1）≥14.

图1 与P2Pn的子图同构的H1Fig.1 H1that is isomorphic with a subgraph of P2Pn

再证明 χS′（P2Pn）≤14.只需给出 P2Pn的一种使用14种颜色的强边染色即可.设P2Pn的顶点集为 V={vi，j|i=1、2；j=1，2，3，…，n}，将 P2Pn的边分为 4 个子集合 E1、E2、E3、E4，其中：

定义P2Pn的一个边染色f.

（1）在E1上：若j≡1（mod3），则f（v1，jv1，j+1）=7；若j≡2（mod3），则f（v1，jv1，j+1）=8；若j≡0（mod3），则f（v1，jv1，j+1）=9；若j≡1（mod3），则f（v2，jv2，j+1）=10；若j≡2（mod3），则f（v2，jv2，j+1）=11；若j≡0（mod3），则f（v2，jv2，j+1）=12.

（2）在E2上：若j≡1（mod2），则f（v1，jv2，j）=13；若j≡0（mod2），则f（v1，jv2，j）=14.

（3）在E3上：若j≡1（mod3），则f（v1，jv2，j+1）=1；若j≡2（mod3），则f（v1，jv2，j+1）=3；若j≡0（mod3），则f（v1，jv2，j+1）=5.

（4）在E4上：若j≡1（mod3），则f（v2，jv1，j+1）=2；若j≡2（mod3），则f（v2，jv1，j+1）=4；若j≡0（mod3），则f（v2，jv1，j+1）=6.

图P2P6在f之下的边染色如图2所示，不难验证 f是一个强边染色.综上有 χS′（P2Pn）≤14.故χS′（P2Pn）=14.

图2 图P2P6的强边染色Fig.2 Strong edge-coloring of P2P6

定理2当n≥3时，χS′（P3Pn）=20.

证明先证明 χS′（P3Pn）≥20.设 H2是一个有12个顶点的图，如图3所示.显然H2中任意2条边之间的距离都不大于1，而图H2含有20条边，所以χS′（H2）≥20.因为 P3Pn有一个子图同构于图 H2，所以χS′（P3Pn）≥χS′（H2）≥20.

图3 与P3Pn的子图同构的H2Fig.3 H2that is isomorphic with a subgraph of P3Pn

再证明 χS′（P3Pn）≤20.只需给出 P3Pn的一种使用20种颜色的强边染色即可.设P3Pn的顶点集为 V={vi，j|i=1、2、3；j=1，2，3，…，n}，将 P3Pn的边分为 4 个子集合 E1、E2、E3、E4，其中：

定义P3Pn的一个边染色f.

（1）在 E1上：当 i≡1（mod2）时，若j≡1（mod3），则f（vi，jvi，j+1）=11，若j≡2（mod3），则f（vi，jvi，j+1）=12，若j≡0（mod3），则f（vi，jvi，j+1）=13；当i=2时，若j≡1（mod3），则f（v2，jv2，j+1）=14，若j≡2（mod3），则f（v2，jv2，j+1）=15，若j≡0（mod3），则f（v2，jv2，j+1）=16.

（2）在E2上：若j≡1（mod2），则f（v1，jv2，j）=17，f（v2，jv3，j）=19；若j≡0（mod2），则f（v1，jv2，j）=18，f（v2，jv3，j）=20.

（3）在 E3上：设 j≡k（mod5）.若k=1、2、3、4，则f（v1，jv2，j+1）=2k-1，若k=0，则f（v1，jv2，j+1）=9；若k=1、2、3，则f（v2，jv3，j+1）=2k+3，若k=4，则f（v2，jv3，j+1）=1，若k=0，则f（v2，jv3，j+1）=3.

（4）在 E4上：设 j≡k（mod5）.若k=1、2、3、4，则f（v2，jv1，j+1）=2k，若k=0，则f（v2，jv1，j+1）=10；若k=1、2，则 f（v3，jv2，j+1）=2k+6，若k=3、4，则 f（v3，jv2，j+1）=2k-4，若k=0，则f（v3，jv2，j+1）=6.

图P3P8在f之下的边染色如图4所示，不难验证 f是一个强边染色.综上有 χS′（P3Pn）≤20.故χS′（P3Pn）=20.

图4 图P3P8的强边染色Fig.4 Strong edge-coloring of P3P8

定理3当n≥4时，χS′（P4Pn）=26.

证明先证明 χS′（P4Pn）≥26.设 H3是一个有16个顶点的图，如图5所示，图H3含有26条边，类似定理2可得χS′（P4Pn）≥χS′（H3）≥26.

图5 与P4Pn的子图同构的H3Fig.5 H3that is isomorphic with a subgraph of P4Pn

再证明 χS′（P4Pn）≤26.只需给出 P4Pn的一种使用26种颜色的强边染色即可.设图P4Pn的顶点集为 V={vi，j|i=1、2、3、4；j=1，2，3，…，n}，将图P4Pn的边分为 4 个子集合 E1、E2、E3、E4，其中：

定义P4Pn的一个边染色f.

（1）在 E1上：当 i≡1（mod2）时，若j≡1（mod3），则f（vi，jvi，j+1）=21，若j≡2（mod3），则f（vi，jvi，j+1）=22，若j≡0（mod3），则 f（vi，jvi，j+1）=23；当 i≡0（mod2）时，若j≡1（mod3），则f（vi，jvi，j+1）=24，若j≡2（mod3），则f（vi，jvi，j+1）=25，若j≡0（mod3），则f（vi，jvi，j+1）=26.

（2）在E2上：若j≡1（mod2），则f（v1，jv2，j）=15，f（v2，jv3，j）=17，f（v3，jv4，j）=19；若j≡0（mod2），则f（v1，jv2，j）=16，f（v2，jv3，j）=18，f（v3，jv4，j）=20.

（3）在 E3上：设 j≡k（mod7）.若k=1、2、3、4、5、6，则f（v1，jv2，j+1）=2k-1，f（v3，jv4，j+1）=2k+1，若k=0，则f（v1，jv2，j+1）=13，f（v3，jv4，j+1）=1；若k=1、2、3，则f（v2，jv3，j+1）=2k+7，若k=4、5、6，则f（v2，jv3，j+1）=2k-7，若k=0，则f（v2，jv3，j+1）=7.

（4）在 E4上：设 j≡k（mod7）.若k=1、2、3、4、5、6，则f（v2，jv1，j+1）=2k，若k=0，则f（v2，jv1，j+1）=14；若k=1、2、3、4，则f（v3，jv2，j+1）=2k+6，若k=5、6，则f（v3，jv2，j+1）=2k-8，若k=0，则f（v3，jv2，j+1）=6；若k=1，则f（v4，jv3，j+1）=14，若k=2、3、4、5、6，则f（v4，jv3，j+1）=2k-2，若k=0，则f（v4，jv3，j+1）=12.

图P4P10在f之下的边染色如图6所示，不难验证 f是一个强边染色.综上有 χS′（P4Pn）≤26.故χS′（P4Pn）=26.

图6 图P4P10的强边染色Fig.6 Strong edge-coloring of P4P10

定理4当m>4，n≥4时，χS′（PmPn）=26.

证明由定理3可知χS′（PmPn）≥26.下面证明χS′（PmPn）≤26.只需给出PmPn的一种使用26种颜色的强边染色即可.设图PmPn的顶点集为V={vi，j|i=1，2，…，m；j=1，2，…，n}，将图 PmPn的边分为 4 个子集合 E1、E2、E3、E4，其中：

定义PmPn的一个边染色f.

（1）在 E1上：当 i≡1（mod2）时，若j≡1（mod3），则f（vi，jvi，j+1）=21，若j≡2（mod3），则f（vi，jvi，j+1）=22，若j≡0（mod3），则 f（vi，jvi，j+1）=23；当 i≡0（mod2）时，若j≡1（mod3），则 f（vi，jvi，j+1）=24，若j≡2（mod3），则f（vi，jvi，j+1）=25，若j≡0（mod3），则f（vi，jvi，j+1）=26.

（2）在 E2上：当 i≡1（mod3）时，若j≡1（mod2），则f（vi，jvi+1，j）=15，若j≡0（mod2），则f（vi，jvi+1，j）=16；当i≡2（mod3）时，若j≡1（mod2），则f（vi，jvi+1，j）=17，若j≡0（mod2），则f（vi，jvi+1，j）=18；当i≡0（mod3）时，若j≡1（mod2），则f（vi，jvi+1，j）=19，若j≡0（mod2），则f（vi，jvi+1，j）=20.

（3）在 E3上：设 j≡k（mod7）.当 i≡1（mod7）时，若k=1、2、3、4、5、6，则f（vi，jvi+1，j+1）=2k-1，若k=0，则f（vi，jvi+1，j+1）=13；当i≡2（mod7）时，若k=1、2、3，则f（vi，jvi+1，j+1）=2k+7，若k=4、5、6，则f（vi，jvi+1，j+1）=2k-7，若k=0，则f（vi，jvi+1，j+1）=7；当i≡3（mod7）时，若k=1、2、3、4、5、6，则f（vi，jvi+1，j+1）=2k+1，若k=0，则f（vi，jvi+1，j+1）=1；当i≡4（mod7）时，若k=1、2，则f（vi，jvi+1，j+1）=2k+9，若k=3、4、5、6，则f（vi，jvi+1，j+1）=2k-5，若k=0，则f（vi，jvi+1，j+1）=9；当i≡5（mod7）时，若k=1、2、3、4、5，则f（vi，jvi+1，j+1）=2k+3，若k=6，则f（vi，jvi+1，j+1）=1，若k=0，则f（vi，jvi+1，j+1）=3；当i≡6（mod7）时，若k=1，则f（vi，jvi+1，j+1）=13，若k=2、3、4、5、6，则f（vi，jvi+1，j+1）=2k-3，若k=0，则f（vi，jvi+1，j+1）=11；当i≡0（mod7）时，若k=1、2、3、4，则f（vi，jvi+1，j+1）=2k+5，若k=5、6，则f（vi，jvi+1，j+1）=2k-9，若k=0，则f（vi，jvi+1，j+1）=5.

（4）在 E4上：设 j≡k（mod7）.当 i≡1（mod7）时，若k=1、2、3、4、5、6，则f（vi+1，jvi，j+1）=2k，若k=0，则f（vi+1，jvi，j+1）=14；当i≡2（mod7）时，若k=1、2、3、4，则f（vi+1，jvi，j+1）=2k+6，若k=5、6，则f（vi+1，jvi，j+1）=2k-8，若k=0，则f（vi+1，jvi，j+1）=6；当i≡3（mod7）时，若k=1，则f（vi+1，jvi，j+1）=14，若k=2、3、4、5、6，则f（vi+1，jvi，j+1）=2k-2，若k=0，则f（vi+1，jvi，j+1）=12；当i≡4（mod7）时，若k=1、2、3、4、5，则f（vi+1，jvi，j+1）=2k+4，若k=6，则f（vi+1，jvi，j+1）=2，若k=0，则f（vi+1，jvi，j+1）=4；当i≡5（mod7）时，若k=1、2，则f（vi+1，jvi，j+1）=2k+10，若k=3、4、5、6，则f（vi+1，jvi，j+1）=2k-4，若k=0，则f（vi+1，jvi，j+1）=10；当i≡6（mod7）时，若k=1、2、3、4、5、6，则f（vi+1，jvi，j+1）=2k+2，若k=0，则f（vi+1，jvi，j+1）=2；当i≡0（mod7）时，若k=1、2、3，则f（vi+1，jvi，j+1）=2k+8，若k=4、5、6，则f（vi+1，jvi，j+1）=2k-6，若k=0，则f（vi+1，jvi，j+1）=8.

图P10P10在f之下的边染色如图7所示，不难验证f是一个强边染色.综上有χS′（PmPn）≤26.故χS′（PmPn）=26.

图7 图P10P10的强边染色Fig.7 Strong edge-coloring of P10P10