若干图的广义字典积的全染色

田双亮，孙向涛

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

0 引言

本文所考虑的图G都是有限无向的简单图，用V（G），E（G）分别表示G的点和边的集合.并用Δ（G）表示G的最大度.本文未给出的其他定义可参考文献［1］.

定义1［2］设G 是具有顶点集V（G）＝｛t1，…，tn｝，n≥2的图，hn＝（Hi）i∈｛1，2，…，n｝是顶点不相交图的序列，其中图 Hi的顶点集为V（Hi）＝｛（ti，y1），…，（ti，yx）｝，x≥1.称G［hn］为G 与hn＝（Hi）i∈｛1，2，…，n｝的广义字典积，其中G［hn］的顶点集为V（G［hn］）＝∪ni＝1V（Hi），且两个顶点（ti，yp）与（tj，yq）相邻当且仅当ti＝tj且（ti，yp）（ti，yq）∈E（Hi），或（ti，tj）∈E（G）.若 Hi≅H 对于i＝1，2，…，n，则G［hn］记为G［H］，且称G［H］为G与H的字典积.

两个顶点不相交图G1与G2的联图［1］是指在G1与G2的并图中，把G1的每个顶点和G2的每个顶点连接起来所得到的图，记为G1∨G2.由广义字典积的定义知，联图G1∨G2是2阶路P2与h2＝（G1，G2）的广义字典积P2［h2］.G 与hn＝（Hi）i∈｛1，2，…，n｝的广义字典积G［hn］也可称为不相交图 H1，H2，…，Hn关于G 的广义联图［3］.G与H 的字典积G［H］可称为H关于G的等广义联图.完全多部图可看成是若干零图的关于完全图的广义联图，而多重联图［4］则可看成是若干个图关于完全图的广义联图.

图G的一个全染色［5］σ是从V（G）∪E（G）到C的映射，且满足条件：（1）没有相邻的两条边或两个顶点具有相同的像；（2）G的每个顶点v的像与v关联的边的像不同.若σ∶V（G）∪E（G）→C是G的全染色，且｜C｜＝k是一个整数，则称G是可k-全染色的.使G可k-全染色的最小的k值，称为G的全色数，记为χT（G）.

1965年，Behzad在文献［5］中提出了全染色的概念，研究了一些特殊图类的全色数，在此基础上提出了图的全色数猜想：对任意的图G，有χT（G）≤Δ（G）＋2.文献［5-7］研究了图的全染色.本文主要研究一些特殊图的广义字典积G［hn］的全染色.在后面的讨论中要用到以下引理：

引理1［5］对图G 的任意子图H，有χT（H）≤χT（G）.

由引理1与引理2，对任意n阶简单图H，若n为奇数，则H的全色数不超过n；若n为偶数，H的全色数不超过n＋1，且对H的任一（n＋1）-全染色，n＋1种颜色中必存在一种颜色c，使得H的所有顶点均不染颜色c.

1 主要结论及其证明

设n阶轮Wn的顶点集和边集分别为

n阶扇Fn与星Sn分别可由轮Wn删去一些边得到.为叙述方便，令V（Hi）＝｛（ti，yj）｜j＝1，2，…，m｝，并记vij＝（ti，yj）.在G［hn］中，用Gkl表示具有二分类（V（Hk），V（Hl））的m-正则二部图.

下面我们研究G 为轮Wn，或扇Fn，或星Sn时广义字典积G［hn］的全色数，其中hn＝（Hi）i∈｛0，1，…，n-1｝，n≥5，Hi为m 阶简单图，i＝0，1，…，n-1.

若G是n阶的轮即G＝Wn，由图的广义字典积的定义，我们可将图G［hn］分解为三个边不交子图G（1），G（2）与G（3），即

定理1 设G 为n 阶轮，或扇，或星，其中n≥5.在hn＝（Hi）i∈｛0，1，…，n-1｝中，｜Hi｜＝m 对于i＝0，1，…，n-1.若H0为m 阶完全图的补图，则χT（G［hn］）＝（n-1）m＋1.

证明 显然，χT（G［hn］）≥Δ（G［hn］）＋1＝（n-1）m＋1.因此，需证明χT（G［hn］≤（n-1）m＋1.因Fn与Sn均为Wn的子图，所以Sn［hn］⊆Fn［hn］⊆Wn［hn］.由引理1，仅需证明，当G＝Wn时，χT（G［hn］）≤（n-1）m＋1.

首先，对G（1）进行正常全染色.由引理1与引理2，可用Ci-1∪｛a｝中的m＋1种色对Hi进行正常全染色，使得Hi的所有顶点均不杂颜色a，其中i＝1，2，…，n-1.并用颜色a染H0的每一顶点.

其次，对G（2）进行正常边染色.用Ci（下标取模n-1）中m种颜色对m-正则二部图G0i进行正常边染色，其中i＝1，…，n-1.

最后，对G（3）进行正常边染色.用Ci＋2（下标取模n-1）中m 种颜色对m-正则二部图Gi，i＋1进行正常边染色，其中i＝1，2，…，n-2.并用C2的m 种颜色对m-正则二部图Gn-1，1进行正常边染色.

容易看出，以上染色σ是G［hn］的一个（（n-1）m＋1）-正常全染色，所以有χT（G［hn］）≤（n-1）m＋1.因此，定理结论成立.

定理2 设G 为n 阶轮，或扇，或星，其中n≥5.在hn＝（Hi）i∈｛0，1，…，n-1｝中，｜Hi｜＝m 对于i＝0，1，…，n-1.若H0为m 阶完全图，则χT（G［hn］）＝mn.

证明 显然，χT（G［hn］）≥Δ（G［hn］）＋1＝mn.与定理1的证明类似，仅需证明，当G＝Wn时，有χT（G［hn］）≤mn.

情况1 m 为奇数.在G［hn］中，G（2）与G（3）的染色与定理1证明中的染色相同.由引理1与引理2，可用Ci-1中的m种颜色对Hi进行正常全染色，其中i＝0，1，…，n-2；用Cn-1中的m种颜色对H0进行正常全染色.显然，以上染色为G［hn］的一个mn-正常全染色.

情况2 m 为偶数.在G［hn］中，G（2）-E（G01）与G（3）的染色与定理1证明中的染色相同.由引理1与引理2，可用Ci-1∪｛cn-1，0｝中的m＋1种颜色对 Hi进行正常全染色，使得 Hi的所有顶点均不染颜色cn-1，0，其中i＝2，3，…，n-1；并用C0∪｛c1，0｝中的m＋1种颜色对H1进行正常全染色，使得H1的所有顶点均不染颜色c1，0.然后，用Cn-1∪｛c1，0｝的m＋1种颜色对H0进行正常全染色，使得H0的所有顶点均不染颜色c1，0，具体地，当k＋l≠m＋1时，令

显然，在 H0的染色中，颜色cn-1，k-1不在顶点v0k上表现，所以可取G01的一个完美匹配 M＝｛v0kv1k｜k＝1，2，…，m｝，并用颜色cn-1，k-1染边v0kv1k，其中k＝1，2，…，m.因G01-M 为（m-1）-正则二部图，所以可用C1-｛c1，0｝中的m-1种颜色对G01-M 进行正常边染色.

容易看出，以上染色是G［hn］的一个mn-全染色，所以有χT（G［hn］）≤mn.因此，定理结论成立.

定理3 设G 为n 阶轮，或扇，或星，其中n≥5.在hn＝（Hi）i∈｛0，1，…，n-1｝中，｜Hi｜＝m 对于i＝0，1，…，n-1.若H0是m 阶二部图，且Δ（H0）≥2，则χT（G［hn］）＝Δ（H0）＋（n-1）m＋1.

证明 设 H0具有二分类（X，Y），且记Δ0＝Δ（H0）.显然，χT（G［hn］）≥Δ（G［hn］）＋1＝Δ0＋（n-1）m＋1.与定理1的证明类似，我们仅需证明，当G＝Wn时，χT（G［hn］）≤Δ0＋（n-1）m＋1.

首先，对G（1）进行正常全染色.因H0是具有最大度Δ0的二部图，所以可用颜色a0染X中的每一顶点，用颜色a1染Y 中的每一顶点，并用Cn-1∪｛c1，0｝中其他Δ0种颜色对 H0进行正常边染色.用Ci-1∪｛a2｝中的m＋1种颜色对Hi进行正常全染色，使得Hi的所有顶点均不染颜色a2，其中i＝1，2，…，n-1.

显然，在H0的全染色中，颜色a1在X的每一顶点上不表现，颜色a0在Y的每一顶点上不表现.

其次，对G（2）进行正常边染色.取G01的一个完美匹配 M＝｛v0kv1k｜k＝1，2，…，m｝.若v0k∈X，则用颜色a1染色v0kv1k；若v0k∈Y，则用颜色a0染边v0kv1k.并用C1-｛c1，0｝中的m-1种颜色对（m-1）-正则二部图G01-M进行正常边染色.用Ci（下标取模n-1）中m种颜色对m-正则二部图G0i进行正常边染色，i＝2，3，…，n-1.

最后，对G（3）进行正常边染色，染色方法与定理1证明中的相同.

容易看出，以上染色为G［hn］的一个（Δ0＋（n-1）m＋1）-正常全染色，故有χT（G［hn］）≤Δ0＋（n-1）m＋1.因此，χT（G［hn］）＝Δ0＋（n-1）m＋1，即定理结论成立.

定理4 设G 为n 阶轮，或扇，或星，其中n≥5.在hn＝（Hi）i∈｛0，1，…，n-1｝中，｜Hi｜＝m 对于i＝0，1，…，n-1.若H0为m 阶圈，m≥3，则χT（G［hn］）＝（n-1）m＋3.

证明 当m 为偶数时，H0为二部圈，所以H0为二部图.由定理3，χT（G［hn］）＝（n-1）m＋3.

当m 为奇数时，显然，χT（G［hn］）≥Δ（G［hn］）＋1＝（n-1）m＋3.与定理1的证明类似，我们仅需证明，当G＝Wn时，χT（G［hn］）≤（n-1）m＋3.

首先，对G（1）进行正常全染色.由引理1与引理2，用Ci-1中的m种颜色对Hi进行正常全染色，其中i＝1，2，…，n-1.因 H0为奇圈，所以可用Cn-1∪｛c1，0｝中的4种颜色对 H0进行正常全染色，具体地，令

显然，在 H0的全染色中，颜色c1，0不在顶点v0，1，v0，m-1与v0，m上表现，而在顶点v0，2，v0，3，…，v0，m-2上交替地缺少颜色a0与a1.

其次，对G（2）进行正常边染色.取G01的一个完美匹配M＝｛v0kv1k｜k＝1，2，…，m｝，用顶点v0k上未表现的颜色染边v0kv1k.并用C1-｛c1，0｝中的m-1种颜色对（m-1）-正则二部图G01-M 进行正常边染色.用Ci（下标取模n-1）中m种颜色对m-正则二部图G0i进行正常边染色，i＝2，3，…，n-1.

最后，对G（3）进行正常边染色，染色方法与定理1证明中的相同.

容易看出，以上染色为G［hn］的一个（（n-1）m＋3）-正常全染色，所以有χT（G［hn］）≤（n-1）m＋3.因此，χT（G［hn］）＝（n-1）m＋3，即定理成立.

［1］Bondy J A，Murty U S R.Graph Theory with Application［M］.New York：American Elsevier，1976.

［2］Waldemar Szumny，Iwona Włyoch，Andrzej Włoch.On the Existence and on the Number of（k，l）-kernels in the Lexicographic Product of Graphs［J］.Discrete Mathematics，2008，308：4616-4624.

［3］Tian Shuang-liang.Star Total Colorings of Mycielski’s Graphs of Balanced General Join of Graph［J］.Journal of Shandong University：Natural Science，2009，45（6）：23-26，34.

［4］田双亮，陈萍.若干多重联图的边染色［J］.南开大学学报：自然科学版，2007，40（3）：27-30.

［5］Behzad.Graphs and Their Chromatic Numbers［M］.Doctoral Thesis，Michigan State University，1965.

［6］Kostochka A V.The Total Coloring of Multigraph with Maximal Degree 4［J］.Discrete Mathematics，1977，17：161-163.

［7］Seoung M A.Total Chromatic Numbers［J］.Appl Math Lett，1992，5：37-39.

［8］Yap H P.Total Coloring of Graph［M］.New York：Springer Verlag，1996.