完全三部图的点可约全染色

Vertex Reducible Total Coloring of Complete Tripartite Graphs

摘要

设f:V\left(G\right)\bigcup E\left(G\right)\to \left\{\mathrm{1},\cdots ,k\right\}是图G的一个（非正常）k⁃全染色，其中\mathrm{1}\le k\le \Delta +\mathrm{1}。若对任意两个顶点u,v\in V\left(G\right)且d\left(u\right)=d\left(v\right)时，满足S\left(u\right)=S\left(v\right)，则称f是图G的一个点可约k⁃全染色，其中S\left(u\right)表示顶点u和点u的关联边上分配的颜色组成的色集合。运用图的色集合事先分配法、组合分析法和构造染色法，结合完美匹配探讨了完全三部图K_{m,n,p}的点可约全染色问题，进一步确定了K_{m,n,p}的点可约全色数。

Abstract

Let f:V\left(G\right)\bigcup E\left(G\right)\to \left\{\mathrm{1,2},\cdots ,k\right\} be a non-proper k-total coloring of G,and \mathrm{1}\le k\le \Delta +\mathrm{1}.If for any two adjacent vertices u,v\in V\left(G\right) with d\left(u\right)=d\left(v\right) satisfy S\left(u\right)=S\left(v\right), then f is called a vertex-reducible k-total coloring, where S\left(u\right) denotes the set of colors of edges incident with u together with the color assigned to u. In this paper, the vertex-reducible total coloring of complete tripartite graph K_{m,n,p} is discussed by using the methods of distributing the color sets in advance, analyzing combinatorially, constructing the colorings and perfectly matching the graphs. Furthermore, the vertex-reducible total chromatic number of K_{m,n,p} is obtained.

Graphical abstract

关键词

完全三部图 / 全染色 / 点可约全染色 / 点可约全色数

Key words

complete tripartite graph / total coloring / vertex-reducible total coloring / vertex-reducible total chromatic number

0　 引 言

本文所考虑的图均为简单无向图。设G=(V,E)是一个n阶图，其中V\left(G\right)表示图G的顶点集，E\left(G\right)表示图G的边集。对\forall x\in V\left(G\right)，用d\left(x\right)表示顶点x的度，即与x所关联的边的数目，称\Delta \left(G\right)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{d\left(x\right)|x\in V\left(G\right)\right\}为图G的最大度，有时简写为\Delta；称\delta \left(G\right)=\mathrm{m}\mathrm{i}\mathrm{n}\left\{d\left(x\right)|x\in V\left(G\right)\right\}为图G的最小度，有时简写为\delta。设M是E\left(G\right)的一个子集，若M中任意两条边都没有公共顶点，则称M是G的一个匹配，M中包含的边数称为匹配数；若G没有另外的匹配M^{\text{'}}，使得\mid M^{\text{'}}\mid >\mid M\mid，则称M为G的最大匹配；若对两个最大匹配M_i,M_j\subseteq E\left(G\right)，有M_i\bigcap M_j=\mathrm{\varnothing }，则称M_i,M_j为图G中边不重的最大匹配。对图G中任一顶点v,C\left(v\right)表示点v的关联边上所染颜色组成的色集合；S\left(v\right)表示点v和点v的关联边上所染颜色组成的色集合。

如果一个图G的顶点集V\left(G\right)=V_{\mathrm{1}}\bigcup V_{\mathrm{2}}\bigcup V_{\mathrm{3}}且V_{\mathrm{1}}\bigcap V_{\mathrm{2}}=\mathrm{\varnothing }，V_{\mathrm{1}}\bigcap V_{\mathrm{3}}=\mathrm{\varnothing }，V_{\mathrm{2}}\bigcap V_{\mathrm{3}}=\mathrm{\varnothing }，有\forall u\in V_i,v\in V_j\left(i=\mathrm{1,2},\mathrm{3};j=\mathrm{1,2},\mathrm{3}\right)，当i\ne j时，uv\in E\left(G\right);当i\ne j时,uv\notin E\left(G\right),那么称G为完全三部图。若图G中|V_{\mathrm{1}}|=m，|V_{\mathrm{2}}|=n，|V_{\mathrm{3}}|=p，则简记为K_{m,n,p}。

图的染色问题是将某些研究对象按照一定的规则和条件进行分类的问题，具有广泛的应用背景。2002年，Zhang等^[1]首次提出图的邻点可区别正常边染色及相关猜想，目前关于图的可区别染色的研究已有很多结果^[2，3]。2009年，文献[4]从色集合可区分的相反面出发，提出了点可约边染色、点可约全染色等概念，图G的一个边着色(未必正常)满足度相同的顶点具有相同的色集合，则称该边染色为点可约边染色，简记为\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{C},其中每个点的色集合为该点关联边上能分配的颜色所构成的集合。将所用最多颜色数k\left(\mathrm{1}\le k\le \Delta \left(G\right)\right)称为点可约边色数，记作为{\chi }_{vr}^{\mathrm{\text{'}}}\left(G\right)。下面给出图G的点可约全染色定义。

定义1 简单图G的一个全着色(未必正常)满足度相同的顶点具有相同的色集合，则称该全染色为点可约全染色，简记为\mathrm{V}\mathrm{R}\mathrm{T}\mathrm{C}，其中每个点的色集合为该点及其关联边上能分配的颜色所构成的集合。将所用最多颜色数k\left(\mathrm{1}\le k\le \Delta \left(G\right)+\mathrm{1}\right)称为点可约全色数，记为{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}\left(G\right)。

近年来，图的可约染色也成为正在研究的运筹方向热门课题，越来越多的学者投身其中。文献[5]通过组合分析法和构造函数法刻画了r⁃正则图、完全图、圈及一些连图等的可约染色。文献[6]研究了星扇轮等联图的邻点可约边染色并确定了其可约色数。文献[7，8]利用色集合事先分配法和反证法讨论了完全三部图K_{\mathrm{2,3},p}和K_{\mathrm{3,3},p}的点可区别\mathrm{I}\mathrm{E}⁃全染色及一般全染色并给出了其具体色数。文献[9]在已有染色概念的基础上，提出了点和可约边染色的概念，运用算法得到了19点以内的树图、路图、圈图、星图、风筝图、友谊图以及这些特殊图组合得到的联图的具体点和可约边色数。

基于目前对可约染色以及完全三部图染色的研究，本文考虑了完全三部图K_{m,n,p}的点可约全染色，运用组合分析法、色集合事先分配法、反证法、构造染色法,并结合完美匹配定理及集合运算性质探讨了完全三部图K_{m,n,p}的点可约全染色问题，得到了如下结果。

定理1 对完全三部图K_{m,n,p}，不妨设m\le n\le p，

（1） 当时，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}\left(K_{m,n,p}\right)=\left\{\begin{array}{l}\Delta +\mathrm{1},\\ m+n+\mathrm{2},\end{array}\right.\begin{array}{c}p=m+\mathrm{1}\\ p>m+\mathrm{1}\end{array}

（2） 当时，

（3） 当时，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}\left(K_{m,n,p}\right)=\left\{\begin{array}{l}\Delta +\mathrm{1},\\ \mathrm{2}m+n+\mathrm{3},\end{array}\right.\begin{array}{c}p\le \mathrm{2}m+\mathrm{2}\\ p>\mathrm{2}m+\mathrm{2}\end{array}

（4） 当m=n=p时，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}\left(K_{m,n,p}\right)=\Delta +\mathrm{1}

1　 准备工作

值得注意的是，在本文提及或要给出一个图的k⁃VRTC或k⁃VREC时，总认为所使用的颜色为\mathrm{1,2},\cdots ,k。

引理1 对于连通图G，设G的最大度为\Delta \left(G\right)，则{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}\left(G\right)+\mathrm{1}\le {\chi }_{vrt}\left(G\right)\le \Delta \left(G\right)+\mathrm{1}。

证 根据定义1，显然可得图G的点可约全色数的一个上界为\Delta \left(G\right)+\mathrm{1}。

下证{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}\left(G\right)\ge {\chi }_{vr}^{\text{'}}\left(G\right)+\mathrm{1}。由定义1知，点可约全染色可看作在点可约边染色的基础上对顶点进行染色。此时，考虑点可约全染色至少会增加一种新色，使得同度点色集合相同。故{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}\left(G\right)\ge {\chi }_{vr}^{\text{'}}\left(G\right)+\mathrm{1}。

又由{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}\left(G\right)+\mathrm{1}\le \Delta \left(G\right)+\mathrm{1}，综上，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}\left(G\right)+\mathrm{1}\le {\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}\left(G\right)\le \Delta \left(G\right)+\mathrm{1}。

引理2^[10] 若G是k-正则二部图，则G存在k个边不重复的完美匹配。

断言1 当时,任意\left(m+\mathrm{1}\right)⁃子集，\left(m+\mathrm{2}\right)⁃子集，\dots，n⁃子集均不为图K_{m,n}的\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{C}色集合。

证 假设结论不成立，若存在某个n⁃子集为图K_{m,n}的\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{C}色集合，则E\left(X\right)一定是正常边染色，且对\forall x\in X，有C\left(x\right)=\left\{\mathrm{1,2},\cdots ,n\right\}。取点x_{\mathrm{1}}\in X，用n种色对边集E\left(x_{\mathrm{1}}\right)进行染色，令f\left(x_{\mathrm{1}}{y}_j\right)=j\left(j=\mathrm{1,2},\cdots ,n\right)。此时，对\forall u,v\in Y，为d\left(u\right)=d\left(v\right)时满足C\left(u\right)=C\left(v\right)，必有\left\{\mathrm{1,2},\cdots ,n\right\}\subseteq C\left(u\right)。从而|C\left(u\right)|\ge n>d\left(u\right)=m，矛盾。同理，若存在某个l⁃子集为图K_{m,n}的\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{C}色集合，且，则对\forall x\in X,\mathrm{有}C\left(x\right)=\left\{\mathrm{1,2},\cdots ,l\right\}。取点x_{\mathrm{1}}\in X，用l种色对边集E\left(x_{\mathrm{1}}\right)进行染色，令f(x_{\mathrm{1}}{y}_j)=j\left(j=\mathrm{1,2},\cdots ,l\right)，必有f\left(x_{\mathrm{1}}{y}_j\right)\subseteq \left\{\mathrm{1,2},\cdots ,l\right\}，j=l,\cdots ,n。此时，对\forall u,v\in Y，为d\left(u\right)=d\left(v\right)时满足C\left(u\right)=C\left(v\right)，必有\left\{\mathrm{1,2},\cdots ,l\right\}\subseteqC\left(u\right)。从而|C\left(u\right)|\ge l\ge m+\mathrm{1}>d\left(u\right)=m，矛盾。

引理3 对完全二部图K_{m,n}(m\le n)，有{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}\left(K_{m,n}\right)=m。

证 设K_{m,n}的点集为V\left(K_{m,n}\right)=X\bigcup Y，其中X=\left\{x_i\mid i=\mathrm{1,2},\cdots ,m\right\}，Y=\left\{y_j\mid j=\mathrm{1,2},\cdots ,n\right\}。由点可约边染色定义可知，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}\left(K_{m,n}\right)\le n。下面分和m=n两种情形讨论：

情形1 当时,由断言1可知，任意\left(m+\mathrm{1}\right)⁃子集，\left(m+\mathrm{2}\right)⁃子集，\dots，n⁃子集均不为图K_{m,n}的\mathrm{V}\mathrm{R}\mathrm{E}\mathrm{C}色集合。此时要证{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}\left(K_{m,n}\right)=m，只需给出图K_{m,n}的一个m⁃VREC。考虑完全二部图K_{m,m}和K_{m,n-m}。注意到粘合两个图中相应的顶点x_i\left(i=\mathrm{1,2},\cdots ,m\right)，可得到所需的K_{m,n}。对图K_{m,m}，由引理2可知，K_{m,m}存在m个边不重复的完美匹配，记为M_i\left(i=\mathrm{1,2},\cdots ,m\right)。令f_{\mathrm{1}}\left(M_i\right)=i\left(i=\mathrm{1,2},\cdots ,m\right)，各点的色集合均为\left\{\mathrm{1,2},\cdots ,m\right\}，记染色方案为f_{\mathrm{1}}；对图K_{m,n-m}，用\left\{\mathrm{1,2},\cdots ,m\right\}中的m种色对点y_j\left(j=m+\mathrm{1},m+\mathrm{2},\cdots ,n\right)的关联边循环染色，使得C\left(y_j\right)=\left\{\mathrm{1,2},\cdots ,m\right\},j=m+\mathrm{1},m+\mathrm{2},\cdots ,n，记染色方案为f_{\mathrm{2}}。在f_{\mathrm{1}}和f_{\mathrm{2}}的构造下，对\forall x\in X,y\in Y,\mathrm{有}C\left(x\right)=\left\{\mathrm{1,2},\cdots ,m\right\}，C\left(y\right)=C\left(y\right)=\left\{\mathrm{1,2},\cdots ,m\right\},满足同度点的色集合相同。显然{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}\left(K_{m,n}\right)=m。

情形2 当m=n时，则K_{m,n}为m⁃正则二部图。根据引理2可知,K_{m,n}是m⁃正常边可染的，且各个点的色集合相同。因此，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}\left(K_{m,n}\right)=m。

引理4^[10] 若G是简单图，则{\chi }^{\text{'}}\left(G\right)=\Delta或{\chi }^{\text{'}}\left(G\right)=\Delta +\mathrm{1}。

2　 定理1的证明

设K_{m,n,p}的顶点集为V\left(K_{m,n,p}\right)=X\bigcup Y\bigcup Z，其中,X=\left\{x_i\left|i=\mathrm{1},\cdots ,m\right.\right\}，Y=\left\{y_j\left|j=\mathrm{1},\cdots ,n\right.\right\}，Z=\left\{z_t\mid t=\mathrm{1,2},\cdots ,p\right\}；边集为E\left(K_{m,n,p}\right)=E_{\mathrm{1}}\bigcup E_{\mathrm{2}}\bigcup E_{\mathrm{3}}，其中,E_{\mathrm{1}}=\left\{x_i{y}_j\left|i=\mathrm{1},\cdots ,m;j=\mathrm{1},\cdots ,n\right.\right\}，E_{\mathrm{2}}=\left\{x_i{z}_t\left|i=\mathrm{1},\cdots ,m;t=\mathrm{1},\cdots ,p\right.\right\}，E_{\mathrm{3}}=\left\{y_j{z}_t\left|j=\mathrm{1},\cdots ,n;t=\mathrm{1},\cdots ,p\right.\right\}。对图K_{m,n,p}的点集X及点集X所关联的边用k\left(k\le \Delta \left(K_{m,n,p}\right)+\mathrm{1}\right)种色进行点可约全染色时，我们规定点集X上出现同一种色，点集X所关联的边上出现余下k-\mathrm{1}种色为好情况；点集X上至少出现\mathrm{2}种色，点集X所关联的边上出现k种色为坏情况。由引理1可知，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}\left(K_{m,n,p}\right)\le \Delta +\mathrm{1}。下面分\mathrm{4}种情形讨论。

情形1 当时

情形1.1 当p>m+\mathrm{1}时

断言2 任意\left(m+n+\mathrm{3}\right)⁃子集，\left(m+n+\mathrm{4}\right)⁃子集，\cdots，\left(\mathrm{2}n+\mathrm{1}\right)⁃子集均不为图K_{m,n,p}的\mathrm{V}\mathrm{R}\mathrm{T}\mathrm{C}色集合。

证 反证法。假设存在某个l⁃子集为图K_{m,n,p}的\mathrm{V}\mathrm{R}\mathrm{T}\mathrm{C}色集合，其中m+n+\mathrm{3}\le l\le \mathrm{2}n+\mathrm{1}。

不妨令该l⁃子集出现在最大度点集X中任一点上。用该l⁃子集中的l种色对最大度点集X及点集X所关联的边进行点可约全染色。好情况是点集X上出现同一种色，点集X所关联的边上出现余下l-\mathrm{1}种色，对\forall x\in X，有C(x)=\{\mathrm{1,2},\dots ,l-\mathrm{1}\}。对\forall u,v\in (Y\bigcup Z)，为d(u)=d(v)时满足S(u)=S(v)，必有\{\mathrm{1,2},\cdots ,l-\mathrm{1}\}\subseteq S(u)。从而|S(u)|\ge l-\mathrm{1}。由d(u)=m+n，得，矛盾。而坏情况是点集X上至少出现\mathrm{2}种色，点集X所关联的边上出现l种色，对\forall x\in X，有C(x)=\{\mathrm{1,2},\dots ,l\}。对\forall u,v\in (Y\bigcup Z)，为d(u)=d(v)时满足S(u)=S(v)，必有\{\mathrm{1,2},\cdots ,l\}\subseteq S(u)，从而|S(u)|\ge l。又d(u)=m+n，故，矛盾。

下面给出图K_{m,n,p}的一个(m+n+\mathrm{2})⁃VRTC。考虑完全二部图K_{n,p}和完全二部图K_{m,n+p}。注意到如图\mathrm{1}所示粘合图K_{n,p}、图K_{m,n+p}中的相应的顶点y_j(j=\mathrm{1,2},\cdots ,n)和z_t(t=\mathrm{1,2},\cdots ,p)，可得所需的图K_{m,n,p}。由引理3知，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{n,p})=n，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{m,n+p})=m，则有图K_{m,n,p}的一个(n+m)⁃VREC。再用颜色n+m+\mathrm{1}和n+m+\mathrm{2}分别染点集X和Y\bigcup Z，从而得到了图K_{m,n,p}的一个(m+n+\mathrm{2})-全染色，且满足\forall x\in X,y\in Y,z\in Z，有S(y)=S(z)=\{\mathrm{1,2},\cdots ,n+m,n+m+\mathrm{2}\}，S(x)=\{n+\mathrm{1},n+\mathrm{2},\cdots ,n+m+\mathrm{1}\}。故得到了图K_{m,n,p}的一个(n+m+\mathrm{2})⁃VRTC，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=n+m+\mathrm{2}。

情形1.2 当p=m+\mathrm{1}时

为证{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=\Delta +\mathrm{1}=\mathrm{2}m+\mathrm{3}。考虑完全二部图K_{n,p}和完全二部图K_{m,n+p}。注意到粘合图K_{n,p}、图K_{m,n+p}中的相应的顶点y_j(j=\mathrm{1,2},\cdots ,n)和z_t(t=\mathrm{1,2},\cdots ,p)，可得所需的图K_{m,n,p}。由引理3知，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{n,p})=n=m+\mathrm{1}，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{m,n+p})=m，则有图K_{m,n,p}的一个(\mathrm{2}m+\mathrm{1})⁃VREC。最后用颜色\mathrm{2}m+\mathrm{2}和\mathrm{2}m+\mathrm{3}分别染点集X和Y\bigcup Z。从而得到了图K_{m,n,p}的(\mathrm{2}m+\mathrm{3})-全染色，且满足\forall x\in X,y\in Y,z\in Z，有S(y)=S(z)=\left\{\mathrm{1},\cdots ,\mathrm{2}m+\mathrm{1,2}m+\mathrm{3}\right\}，S(x)=\{m+\mathrm{2},m+\mathrm{3},\cdots ,\mathrm{2}m+\mathrm{1,2}m+\mathrm{2}\}。故得到了图K_{m,n,p}的一个(\mathrm{2}m+\mathrm{3})⁃VRTC，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=\mathrm{2}m+\mathrm{3}。

情形2 当时

情形2.1 当p\ge \mathrm{2}m+\mathrm{2}时

断言3 任意\left(\mathrm{3}m+\mathrm{3}\right)⁃子集，\left(\mathrm{3}m+\mathrm{4}\right)⁃子集，\cdots，\left(m+p+\mathrm{1}\right)⁃子集均不为图K_{m,n,p}的\mathrm{V}\mathrm{R}\mathrm{T}\mathrm{C}色集合。

证 反证法。假设存在某个l⁃子集为图K_{m,n,p}的\mathrm{V}\mathrm{R}\mathrm{T}\mathrm{C}色集合，其中\mathrm{3}m+\mathrm{3}\le l\le m+p+\mathrm{1}。不妨令该l⁃子集出现在最大度点集X\bigcup Y中任一点上。用该l⁃子集中的l种色对最大度点集X和Y及点集X和Y所关联的边进行点可约全染色。下面分好情况和坏情况进行讨论。

（1） 好情况是点集X\bigcup Y上出现同一种色，点集X和Y所关联的边上出现余下l-\mathrm{1}色，对\forall u\in (X\bigcup Y)，有C(u)=\{\mathrm{1,2},\cdots ,l-\mathrm{1}\}。任选C_{\mathrm{1}}\subseteq C(u)，|C_{\mathrm{1}}|\le l-\mathrm{1}，C_{\mathrm{2}}\subseteq C(u)，|C_{\mathrm{2}}|\le l-\mathrm{1}且C_{\mathrm{1}}\bigcup C_{\mathrm{2}}=C(u)。将C_{\mathrm{1}}分配给E_{\mathrm{1}}，C_{\mathrm{2}}分配给E_{\mathrm{2}}。对\forall z,w\in Z，为d(z)=d(w)时满足S(z)=S(w)，再任选C_{\mathrm{3}}\subseteq C_{\mathrm{1}}且|C_{\mathrm{3}}|=|C_{\mathrm{1}}|-m，必有(C_{\mathrm{2}}\bigcup C_{\mathrm{3}})\subseteq S(z)\mathrm{。}根据C_{\mathrm{1}}\bigcap C_{\mathrm{2}}=\mathrm{\varnothing }和C_{\mathrm{1}}\bigcap C_{\mathrm{2}}\ne \mathrm{\varnothing }进行分类讨论。

(1.1) 当C_{\mathrm{1}}\bigcap C_{\mathrm{2}}=\mathrm{\varnothing }，分情形C_{\mathrm{3}}=\mathrm{\varnothing }和C_{\mathrm{3}}\ne \mathrm{\varnothing }讨论。

若C_{\mathrm{3}}=\mathrm{\varnothing }，则|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=C_{\mathrm{2}}|\ge l-m|；

若C_{\mathrm{3}}\ne \mathrm{\varnothing }，则|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|=l-m。

(1.2) 当C_{\mathrm{1}}\bigcap C_{\mathrm{2}}\ne \mathrm{\varnothing }，分情形C_{\mathrm{3}}=\mathrm{\varnothing }和C_{\mathrm{3}}\ne \mathrm{\varnothing }讨论。

若C_{\mathrm{3}}=\mathrm{\varnothing }，则|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|\ge l-m；

若C_{\mathrm{3}}\ne \mathrm{\varnothing }，又分C_{\mathrm{3}}=C_{\mathrm{1}}\bigcap C_{\mathrm{2}}和C_{\mathrm{3}}\ne C_{\mathrm{1}}\bigcap C_{\mathrm{2}}两种情形讨论。

(1.2.1) 当C_{\mathrm{3}}=C_{\mathrm{1}}\bigcap C_{\mathrm{2}}，则C_{\mathrm{3}}\subseteq C_{\mathrm{2}}，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|\ge l-\mathrm{1}-m。

(1.2.2) 当C_{\mathrm{3}}\ne C_{\mathrm{1}}\bigcap C_{\mathrm{2}}，若C_{\mathrm{2}}\bigcap C_{\mathrm{3}}=\mathrm{\varnothing }，则|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|\ge l-\mathrm{1}-m；若C_{\mathrm{2}}\bigcap C_{\mathrm{3}}\ne \mathrm{\varnothing }，则|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|-|C_{\mathrm{2}}\bigcap C_{\mathrm{3}}|\ge l-\mathrm{1}-m。

综上，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|-|C_{\mathrm{2}}\bigcap C_{\mathrm{3}}|\ge l-\mathrm{1}-m，故|S(z)|\ge |C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|\ge l-\mathrm{1}-m。又d(z)=\mathrm{2}m，则，矛盾。

（2） 坏情况是点集X\bigcup Y上至少出现\mathrm{2}种色，点集X\bigcup Y所关联的边上出现l种色，对\forall u\in (X\bigcup Y)，有C(u)=\{\mathrm{1,2},\cdots ,l\}。任选C_{\mathrm{1}}\subseteq C(u)，|C_{\mathrm{1}}|\le l，C_{\mathrm{2}}\subseteq C(u)，|C_{\mathrm{2}}|\le l且C_{\mathrm{1}}\bigcup C_{\mathrm{2}}=C(u)，将C_{\mathrm{1}}分配给E_{\mathrm{1}}，C_{\mathrm{2}}分配给E_{\mathrm{2}}。对\forall z,w\in Z，为d(z)=d(w)时满足S(z)=S(w)，再任选C_{\mathrm{3}}\subseteq C_{\mathrm{1}}且|C_{\mathrm{3}}|=|C_{\mathrm{1}}|-m-\mathrm{1}，必有(C_{\mathrm{2}}\bigcup C_{\mathrm{3}})\subseteq S(z)。根据C_{\mathrm{1}}\bigcap C_{\mathrm{2}}=\mathrm{\varnothing }和C_{\mathrm{1}}\bigcap C_{\mathrm{2}}\ne \mathrm{\varnothing }进行分类讨论。

(2.1) 当C_{\mathrm{1}}\bigcap C_{\mathrm{2}}=\mathrm{\varnothing }，若C_{\mathrm{3}}=\mathrm{\varnothing }，则|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|\ge l-m-\mathrm{1}；若C_{\mathrm{3}}\ne \mathrm{\varnothing }，则|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|=l-m-\mathrm{1}。

(2.2) 当C_{\mathrm{1}}\bigcap C_{\mathrm{2}}\ne \mathrm{\varnothing }，分情形C_{\mathrm{3}}=\mathrm{\varnothing }和C_{\mathrm{3}}\ne \mathrm{\varnothing }讨论。

若C_{\mathrm{3}}=\mathrm{\varnothing }，则|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|\ge l-m-\mathrm{1}；

若C_{\mathrm{3}}\ne \mathrm{\varnothing }，又分C_{\mathrm{3}}=C_{\mathrm{1}}\bigcap C_{\mathrm{2}}和C_{\mathrm{3}}\ne C_{\mathrm{1}}\bigcap C_{\mathrm{2}}两种情形讨论。

(2.2.1) 当C_{\mathrm{3}}=C_{\mathrm{1}}\bigcap C_{\mathrm{2}}，则C_{\mathrm{3}}\subseteq C_{\mathrm{2}}，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|\ge l-m-\mathrm{1}。

(2.2.2) \mathrm{当}{C}_{\mathrm{3}}\ne C_{\mathrm{1}}\bigcap C_{\mathrm{2}}，\mathrm{若}{C}_{\mathrm{2}}\bigcap C_{\mathrm{3}}=\mathrm{\varnothing },\mathrm{则}|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|\ge l-m;\mathrm{若}{C}_{\mathrm{2}}\bigcap C_{\mathrm{3}}\ne \mathrm{\varnothing },\mathrm{则}|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|-(C_{\mathrm{2}}\bigcap C_{\mathrm{3}})\ge l-m。

综上，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|\ge p。故|S(z)|\ge |C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|\ge l-m-\mathrm{1}。又d(z)=\mathrm{2}m，则，矛盾。

下面给出图K_{m,n,p}的一个(\mathrm{3}m+\mathrm{2})⁃VRTC。考虑完全二部图K_{m,n}和K_{m+n,p}。注意到粘合图K_{m,n}、图K_{m+n,p}中相应的顶点x_i(i=\mathrm{1,2},\cdots ,m)和y_j(j=\mathrm{1,2},\cdots ,n)，可得所需的图K_{m,n,p}。由引理3知，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{m,n})=m，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{m+n,p})=m+n=\mathrm{2}m，则有图K_{m,n,p}的一个\mathrm{3}m⁃VREC。再用颜色\mathrm{3}m+\mathrm{1}和\mathrm{3}m+\mathrm{2}分别对图K_{m,n,p}的顶点集X\bigcup Y和Z着色，从而得到了图K_{m,n,p}的(\mathrm{3}m+\mathrm{2})⁃全染色，且满足\forall x\in X,y\in Y,z\in Z，有S(x)=S(y)=\left\{\mathrm{1,2},\cdots ,\mathrm{3}m,\mathrm{3}m+\mathrm{1}\right\}，S(z)=\left\{m+\mathrm{1},m+\mathrm{2},\cdots ,\mathrm{3}m,\mathrm{3}m+\mathrm{2}\right\}。故得到了图K_{m,n,p}一个(\mathrm{3}m+\mathrm{2})⁃VRTC，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=\mathrm{3}m+\mathrm{2}。

情形2.2 当时

为证{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=\Delta +\mathrm{1}=n+p+\mathrm{1}。考虑完全二部图K_{m,n}和完全二部图K_{m+n,p}。注意到粘合图K_{m,n}、图K_{m+n,p}中相应的顶点x_i(i=\mathrm{1,2},\cdots ,m)和y_j(j=\mathrm{1,2},\cdots ,n)可得所需的图K_{m,n,p}。下面分和p\le \mathrm{2}m两种情况讨论。

（1） 当，\mathrm{此}\mathrm{时}p=\mathrm{2}m+\mathrm{1}，\mathrm{由}\mathrm{引}\mathrm{理}\mathrm{3}\mathrm{知},{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{m,n})=m，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{m+n,p})=m+n，则有图K_{m,n,p}的一个(n+\mathrm{2}m)⁃VREC。再用颜色n+\mathrm{2}m+\mathrm{1}和n+\mathrm{2}m+\mathrm{2}分别对图K_{m,n,p}的顶点集X\bigcup Y和Z进行着色，从而得到图K_{m,n,p}的(n+\mathrm{2}m+\mathrm{2})⁃全染色，且\forall x\in X,y\in Y,z\in Z，有S(x)=S(y)=\left\{\mathrm{1,2},\cdots ,n+\mathrm{2}m,n+\mathrm{2}m+\mathrm{1}\right\}，S(z)=\left\{n+\mathrm{1},n+\mathrm{2},\cdots ,n+\mathrm{2}m,n+\mathrm{2}m+\mathrm{2}\right\}。故得到图K_{m,n,p}的一个(n+\mathrm{2}m+\mathrm{2})⁃VRTC，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=n+\mathrm{2}m+\mathrm{2}=\mathrm{\Delta }+\mathrm{1}。

（2） 当p\le \mathrm{2}m时，即，由引理3知，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{m,n})=n，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{p,m+n})=p，则有图K_{m,n,p}的一个(n+p)⁃VREC。再用颜色n+p+\mathrm{1}对图K_{m,n,p}的所有顶点进行着色，从而得到了图K_{m,n,p}的(n+p+\mathrm{1})⁃全染色，且\forall x\in X,y\in Y,z\in Z，有S(x)=S(y)=\left\{\mathrm{1,2},\cdots ,n+p,n+p+\mathrm{1}\right\}，S(z)=\left\{n+\mathrm{1},n+\mathrm{2},\cdots ,n+p,n+p+\mathrm{1}\right\}。故得到了图K_{m,n,p}的一个(n+p+\mathrm{1})⁃VRTC，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=n+p+\mathrm{1}。

情形3 当时

情形3.1 当p>\mathrm{2}m+\mathrm{2}时

断言4 任意\left(\mathrm{2}m+n+\mathrm{4}\right)⁃子集，\left(\mathrm{2}m+n+\mathrm{5}\right)⁃子集，\cdots，\left(n+p+\mathrm{1}\right)⁃子集均不为图K_{m,n,p}的\mathrm{V}\mathrm{R}\mathrm{T}\mathrm{C}色集合。

证 反证法。假设存在某个l⁃子集为图K_{m,n,p}的\mathrm{V}\mathrm{R}\mathrm{T}\mathrm{C}色集合，其中\mathrm{2}m+n+\mathrm{4}\le l\le n+p+\mathrm{1}。不妨令这l种不同的色均出现在最大度点集X中任一点上，用该l⁃子集中的l种色对最大度点集X及点集X的关联边组成的边集E(X)=E_{\mathrm{1}}\bigcup E_{\mathrm{2}}进行点可约全染色。下面分好情况和坏情况进行讨论。

（1） 好情况是点集X上出现同一种色，边集E(X)=E_{\mathrm{1}}\bigcup E_{\mathrm{2}}上出现余下l-\mathrm{1}种色。对\forall x\in X，有C(x)=\{\mathrm{1,2},\cdots ,l-\mathrm{1}\}。任选C_{\mathrm{1}}\subseteq C(x)，|C_{\mathrm{1}}|\le l-\mathrm{1}，C_{\mathrm{2}}\subseteq C(x)，|C_{\mathrm{2}}|\le l-\mathrm{1}，且C_{\mathrm{1}}\bigcup C_{\mathrm{2}}=C(x)。将C_{\mathrm{1}}分配给E_{\mathrm{1}}，C_{\mathrm{2}}分配给E_{\mathrm{2}}。对\forall y,v\in Y，为d(y)=d(v)时满足S(y)=S(v)，必有C_{\mathrm{1}}\subseteq S(y)。对\forall z,w\in Z，为d(z)=d(w)时满足S(z)=S(w)，再任选C_{\mathrm{3}}\subseteq C_{\mathrm{1}}且|C_{\mathrm{3}}|=|C_{\mathrm{1}}|-m-\mathrm{1}，必有(C_{\mathrm{2}}\bigcup C_{\mathrm{3}})\subseteq S(z)。根据C_{\mathrm{1}}\bigcap C_{\mathrm{2}}=\mathrm{\varnothing }和C_{\mathrm{1}}\bigcap C_{\mathrm{2}}\ne \mathrm{\varnothing }对C_{\mathrm{3}}进行分类讨论。

(1.1) 当C_{\mathrm{1}}\bigcap C_{\mathrm{2}}=\mathrm{\varnothing }，若C_{\mathrm{3}}=\mathrm{\varnothing }，则|C_{\mathrm{1}}|=m+\mathrm{1}，|C_{\mathrm{2}}|=l-m-\mathrm{2}，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|=l-m-\mathrm{2}；若C_{\mathrm{3}}\ne \mathrm{\varnothing }，则|C_{\mathrm{1}}|>m+\mathrm{1}，|C_{\mathrm{2}}|=l-\mathrm{1}-|C_{\mathrm{1}}|，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|-|C_{\mathrm{2}}\bigcap C_{\mathrm{3}}|=l-\mathrm{1}-|C_{\mathrm{1}}|+(|C_{\mathrm{1}}|-m-\mathrm{1})-\mathrm{0}=l-m-\mathrm{2}。

(1.2) 当C_{\mathrm{1}}\bigcap C_{\mathrm{2}}\ne \mathrm{\varnothing }，分情形C_{\mathrm{3}}=\mathrm{\varnothing }和C_{\mathrm{3}}\ne \mathrm{\varnothing }讨论。

若C_{\mathrm{3}}=\mathrm{\varnothing }，则|C_{\mathrm{1}}|=m+\mathrm{1}，|C_{\mathrm{2}}|=l-\mathrm{2}-m，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|=l-\mathrm{2}-m。

若C_{\mathrm{3}}\ne \mathrm{\varnothing }，有|C_{\mathrm{1}}|>m+\mathrm{1}，又分C_{\mathrm{3}}=C_{\mathrm{1}}\bigcap C_{\mathrm{2}}和C_{\mathrm{3}}\ne C_{\mathrm{1}}\bigcap C_{\mathrm{2}}两种情形讨论。

(1.2.1) 当C_{\mathrm{3}}=C_{\mathrm{1}}\bigcap C_{\mathrm{2}}，则C_{\mathrm{3}}\subseteq C_{\mathrm{2}}，|C_{\mathrm{2}}|\ge l-\mathrm{2}-m，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|\ge l-\mathrm{2}-m；

(1.2.2) 当C_{\mathrm{3}}\ne C_{\mathrm{1}}\bigcap C_{\mathrm{2}},\mathrm{若}，C_{\mathrm{2}}\bigcap C_{\mathrm{3}}=\mathrm{\varnothing }，则|C_{\mathrm{2}}|\ge l-\mathrm{2}-m，|C_{\mathrm{3}}|\ge \mathrm{1}，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|\ge l-\mathrm{1}-m；若C_{\mathrm{2}}\bigcap C_{\mathrm{3}}\ne \mathrm{\varnothing }，则|C_{\mathrm{2}}|\ge l-\mathrm{2}-m，|C_{\mathrm{3}}|\ge \mathrm{2}，|C_{\mathrm{2}}\bigcap C_{\mathrm{3}}|\ge \mathrm{1}，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|-|C_{\mathrm{2}}\bigcap C_{\mathrm{3}}\ge l-\mathrm{1}-m|。

综上，|S(z)|\ge |C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|\ge l-\mathrm{2}-m。又d(z)=m+n，故，矛盾。

（2） 坏情况是点集X上至少出现\mathrm{2}种不同的色，边集E(X)=E_{\mathrm{1}}\bigcup E_{\mathrm{2}}上出现l种色。对\forall x\in X，有C(x)=\{\mathrm{1,2},\cdots ,l\}。任选C_{\mathrm{1}}\subseteq C(x)，|C_{\mathrm{1}}|\le l，C_{\mathrm{2}}\subseteq C(x)，|C_{\mathrm{2}}|\le l，且C_{\mathrm{1}}\bigcup C_{\mathrm{2}}=C(x)。将C_{\mathrm{1}}分配给E_{\mathrm{1}}，C_{\mathrm{2}}分配给E_{\mathrm{2}}。对\forall y,v\in Y，为d(y)=d(v)时满足S(y)=S(v)，必有C_{\mathrm{1}}\subseteq S(y)。对\forall z,w\in Z，为d(z)=d(w)时满足S(z)=S(w)，再任选C_{\mathrm{3}}\subseteq C_{\mathrm{1}}且|C_{\mathrm{3}}|=|C_{\mathrm{1}}|-m-\mathrm{1}，必有(C_{\mathrm{2}}\bigcup C_{\mathrm{3}})\subseteq S(z)。根据C_{\mathrm{1}}\bigcap C_{\mathrm{2}}=\mathrm{\varnothing }和C_{\mathrm{1}}\bigcap C_{\mathrm{2}}\ne \mathrm{\varnothing }对C_{\mathrm{3}}进行分类讨论。

(2.1) 当C_{\mathrm{1}}\bigcap C_{\mathrm{2}}=\mathrm{\varnothing }，分情形C_{\mathrm{3}}=\mathrm{\varnothing }和C_{\mathrm{3}}\ne \mathrm{\varnothing }讨论。

若C_{\mathrm{3}}=\mathrm{\varnothing }，则|C_{\mathrm{1}}|=m+\mathrm{1}，|C_{\mathrm{2}}|=l-m-\mathrm{1}，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|=l-m-\mathrm{1}；

若C_{\mathrm{3}}\ne \mathrm{\varnothing }，则|C_{\mathrm{1}}|>m+\mathrm{1}，|C_{\mathrm{2}}|=l-|C_{\mathrm{1}}|，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|=(l-|C_{\mathrm{1}}|)+(|C_{\mathrm{1}}|-m-\mathrm{1})=l-m-\mathrm{1}。

(2.2) 当C_{\mathrm{1}}\bigcap C_{\mathrm{2}}\ne \mathrm{\varnothing }，分情形C_{\mathrm{3}}=\mathrm{\varnothing }和C_{\mathrm{3}}\ne \mathrm{\varnothing }讨论。

若C_{\mathrm{3}}=\mathrm{\varnothing }，则|C_{\mathrm{1}}|=m+\mathrm{1}，|C_{\mathrm{2}}|=l-m-\mathrm{1}，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|=l-m-\mathrm{1}；

若C_{\mathrm{3}}\ne \mathrm{\varnothing }，则|C_{\mathrm{1}}|>m+\mathrm{1}，又分C_{\mathrm{3}}=C_{\mathrm{1}}\bigcap C_{\mathrm{2}}和C_{\mathrm{3}}\ne C_{\mathrm{1}}\bigcap C_{\mathrm{2}}两种情形讨论。

(2.2.1) 当C_{\mathrm{3}}=C_{\mathrm{1}}\bigcap C_{\mathrm{2}}，则C_{\mathrm{3}}\subseteq C_{\mathrm{2}}，|C_{\mathrm{2}}|\ge l-m-\mathrm{1}，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|\ge l-m-\mathrm{1}；

(2.2.2) 当C_{\mathrm{3}}\ne C_{\mathrm{1}}\bigcap C_{\mathrm{2}}，若C_{\mathrm{2}}\bigcap C_{\mathrm{3}}=\mathrm{\varnothing }，则|C_{\mathrm{2}}|\ge l-m-\mathrm{1}，|C_{\mathrm{3}}|\ge \mathrm{1}，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|\ge l-m；若C_{\mathrm{2}}\bigcap C_{\mathrm{3}}\ne \mathrm{\varnothing }，则|C_{\mathrm{2}}|\ge l-m-\mathrm{1}，|C_{\mathrm{3}}|\ge \mathrm{2}，|C_{\mathrm{2}}\bigcap C_{\mathrm{3}}|\ge \mathrm{1}，|C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|=|C_{\mathrm{2}}|+|C_{\mathrm{3}}|-|C_{\mathrm{2}}\bigcap C_{\mathrm{3}}|\ge l-m。

综上，|S(z)|\ge |C_{\mathrm{2}}\bigcup C_{\mathrm{3}}|\ge l-m-\mathrm{1}。又d(z)=m+n，故，矛盾。

下面给出图K_{m,n,p}的一个(\mathrm{2}m+n+\mathrm{3})⁃VRTC。考虑完全二部图K_{n,p}和K_{m,n+p}。注意到粘合图K_{n,p}、图K_{m,n+p}中相应的顶点y_j(j=\mathrm{1,2},\cdots ,n)和z_t(t=\mathrm{1,2},\cdots ,p)，可得所需的图K_{m,n,p}。由引理3知，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{n,p})=n，记染色方案为{\psi }_{\mathrm{1}}。因为n\ne p，所以图K_{m,n+p}的点可约边染色不用保证C(y)=C(z)。图K_{m,n+p}，由n\ne p，为使Y中各点色集合相同，用\{n+\mathrm{1},\cdots ,n+m\}这m种色循环染边E_{\mathrm{1}}，记染色方案如下

{\psi }_{\mathrm{2}}\left(y_j{x}_i\right)=\left\{\begin{array}{l}\left(i+j-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)+n,\\ i+n,\end{array}\right.\begin{array}{l}i=\mathrm{1,2},\cdots ,m;j=\mathrm{1,2},\cdots ,m\\ i=\mathrm{1,2},\cdots ,m;j=m+\mathrm{1},m+\mathrm{2},\cdots ,n\end{array}

其中(i+j-\mathrm{1})=m时，将\left(i+j-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)记作m。

为使Z中各点色集合相同，用\{n+m+\mathrm{1},\cdots ,n+\mathrm{2}m\}这m种色循环染边E_{\mathrm{1}}，记染色方案如下

{\psi }_{\mathrm{3}}\left({\mathrm{z}}_t{x}_i\right)=\left\{\begin{array}{l}\left(i+t-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)+n+m,\\ i+n+m,\end{array}\begin{array}{l}i=\mathrm{1,2},\cdots ,m;t=\mathrm{1,2},\cdots ,m;\\ i=\mathrm{1,2},\cdots ,m;t=m+\mathrm{1},m+\mathrm{2},\cdots ,p\end{array}\right.

其中(i+t-\mathrm{1})=m时,将\left(i+j-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)记作m。

综上可得图K_{m,n,p}的一个(\mathrm{2}m+n)⁃VREC。再用颜色\mathrm{2}m+n+\mathrm{1}，\mathrm{2}m+n+\mathrm{2}和\mathrm{2}m+n+\mathrm{3}色分别对图V(K_{m,n,p})的顶点集X、Y和Z进行染色。从而得到了图K_{m,n,p}的(\mathrm{2}m+n+\mathrm{3})⁃全染色，且满足对\forall x\in X,y\in Y,z\in Z，S(x)=\left\{n+\mathrm{1},n+\mathrm{2},\cdots ,n+\mathrm{2}m,n+\mathrm{2}m+\mathrm{1}\right\}，S(y)=\left\{\mathrm{1,2},\cdots ,n+m,\mathrm{2}n+m+\mathrm{2}\right\}，S(z)=\left\{\mathrm{1,2},\cdots ,n,n+m+\mathrm{1},\cdots ,n+\mathrm{2}m,n+\mathrm{2}m+\mathrm{3}\right\}。故得到了图K_{m,n,p}的一个(\mathrm{2}m+n+\mathrm{3})⁃VRTC，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=\mathrm{2}m+n+\mathrm{3}。

情形3.2 当p\le \mathrm{2}m+\mathrm{2}时

为证{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=\Delta +\mathrm{1}=n+p+\mathrm{1}，考虑完全二部图K_{n,p}和K_{m,n+p}。注意到粘合图K_{n,p}、图K_{m,n+p}中相应的顶点y_j(j=\mathrm{1,2},\cdots ,n)和z_t(t=\mathrm{1,2},\cdots ,p)可得所需的图K_{m,n,p}。下面分p=\mathrm{2}m+\mathrm{2}和两种情况讨论。

（1） 当p=\mathrm{2}m+\mathrm{2}，则n+p+\mathrm{1}=\mathrm{2}m+n+\mathrm{3}。由引理3知，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{n,p})=n，记染色方案为{\psi }_{\mathrm{1}}。因为n\ne p，所以图K_{m,n+p}的点可约边染色不用保证C(y)=C(z)。对图K_{m,n+p}，由n\ne p，为使Y中各点色集合相同，用\{n+\mathrm{1},\cdots ,n+m\}这m种色循环染边E_{\mathrm{1}}，记染色方案为

{\psi }_{\mathrm{2}}\left(y_j{x}_i\right)=\left\{\begin{array}{l}\left(i+j-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)+n,\\ i+n,\end{array}\right.\begin{array}{l}i=\mathrm{1,2},\cdots ,m;j=\mathrm{1,2},\cdots ,m\\ i=\mathrm{1,2},\cdots ,m;j=m+\mathrm{1},m+\mathrm{2},\cdots ,n\end{array}

其中(i+j-\mathrm{1})=m时，将\left(i+j-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)记作m。

为使Z中各点色集合相同，用\{n+m+\mathrm{1},\cdots ,n+\mathrm{2}m\}这m种色循环染边E_{\mathrm{1}}，记染色方案为

{\psi }_{\mathrm{3}}\left({\mathrm{z}}_t{x}_i\right)=\left\{\begin{array}{l}\left(i+t-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)+n+m,\\ i+n+m,\end{array}\right.\begin{array}{l}i=\mathrm{1,2},\cdots ,m;t=\mathrm{1,2},\cdots ,m\\ i=\mathrm{1,2},\cdots ,m;t=m+\mathrm{1},m+\mathrm{2},\cdots ,p\end{array}

其中(i+t-\mathrm{1})=m时，将\left(i+t-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)记作m。

综上可得图K_{m,n,p}的一个(\mathrm{2}m+n)⁃VREC。再用颜色\mathrm{2}m+n+\mathrm{1}，\mathrm{2}m+n+\mathrm{2}和\mathrm{2}m+n+\mathrm{3}分别对图V(K_{m,n,p})的顶点集X、Y和Z进行染色。从而得到了图K_{m,n,p}的(n+p+\mathrm{1})-全染色，且满足对\forall x\in X,y\in Y,z\in Z，S(x)=\left\{n+\mathrm{1},n+\mathrm{2},\cdots ,n+\mathrm{2}m,n+\mathrm{2}m+\mathrm{1}\right\}，S(y)=\left\{\mathrm{1,2},\cdots ,n+m,\mathrm{2}n+m+\mathrm{2}\right\}，S(z)=\left\{\mathrm{1,2},\cdots ,n,n+m+\mathrm{1},\cdots ,n+\mathrm{2}m,n+\mathrm{2}m+\mathrm{3}\right\}。故得到了图K_{m,n,p}的一个(\mathrm{2}m+n+\mathrm{3})⁃VRTC, {\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=\mathrm{2}m+n+\mathrm{3}=n+p+\mathrm{1}。

（2） 当时，先用颜色\mathrm{1}，\mathrm{2}，\mathrm{3}这\mathrm{3}种不同的颜色分别对V(K_{m,n,p})的顶点集X、Y和Z进行染色。再由引理3知，{\chi }_{\mathrm{v}\mathrm{r}}^{\text{'}}(K_{n,p})=n，记染色方案为{\psi }_{\mathrm{1}}。因为n\ne p，所以图K_{m,n+p}的点可约边染色不必保证C(y)=C(z)。对图K_{m,n+p}，由n\ne p，为使Y中各点色集合相同，用\{n+\mathrm{4},\cdots ,n+m+\mathrm{3}\}这m种色循环染边E_{\mathrm{1}}，染色方案为

{\psi }_{\mathrm{2}}\left(y_j{x}_i\right)=\left\{\begin{array}{l}\left(i+j-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)+n+\mathrm{3},\\ i+n+\mathrm{3},\end{array}\right.\begin{array}{l}i=\mathrm{1,2},\cdots ,m;j=\mathrm{1,2},\cdots ,m\\ i=\mathrm{1,2},\cdots ,m;j=m+\mathrm{1},m+\mathrm{2},\cdots ,n\end{array}

其中(i+j-\mathrm{1})=m，将\left(i+j-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}m\right)记作m。

为使Z中各点色集合相同，用\{n+m+\mathrm{4},\cdots ,n+p+\mathrm{1}\}这(n+p+\mathrm{1})-(\mathrm{3}+n+m)即 种色循环染边E_{\mathrm{1}}，记染色方案为

{\psi }_{\mathrm{3}}\left({\mathrm{z}}_t{x}_i\right)=\left\{\begin{array}{l}\left(i+t-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}p-m-\mathrm{2}\right)+n+m+\mathrm{3},\\ i+n+m+\mathrm{3},\end{array}\right.\begin{array}{l}i=\mathrm{1,2},\cdots ,m;t=\mathrm{1,2},\cdots ,m\\ i=\mathrm{1,2},\cdots ,m;t=m+\mathrm{1},m+\mathrm{2},\cdots ,p\end{array}

其中(i+t-\mathrm{1})=p-m-\mathrm{2}，将\left(i+t-\mathrm{1}\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}p-m-\mathrm{2}\right)记作p-m-\mathrm{2}。

从而得到了图K_{m,n,p}的(n+p+\mathrm{1})-全染色，且满足对\forall x\in X,y\in Y,z\in Z，S(x)=\left\{\mathrm{1},n+\mathrm{4},\cdots ,n+p+\mathrm{1}\right\}，S(y)=\left\{\mathrm{2,4},\cdots ,n+\mathrm{3},\cdots ,n+m+\mathrm{3}\right\}，S(z)=\left\{\mathrm{3,4},\cdots ,n+\mathrm{3},n+m+\mathrm{4},\cdots ,n+p+\mathrm{1}\right\}。故得到了图K_{m,n,p}一个(n+p+\mathrm{1})⁃VRTC，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=n+p+\mathrm{1}。

情形4 当m=n=p时，由引理4可知，{\chi }^{\text{'}}(K_{m,n,p})=\Delta或{\chi }^{\text{'}}(K_{m,n,p})=\Delta +\mathrm{1}。下面分两种情况讨论。

情形4.1 若{\chi }^{\text{'}}(K_{m,n,p})=\Delta，则K_{m,n,p}是一个\Delta⁃正常边染色，且每个点的色集合都包含这\Delta种色。再用\mathrm{1}种新色对所有顶点进行染色，此时每一点的色集合都包含\mathrm{\Delta }+\mathrm{1}种颜色，即满足\forall u,v\in K_{m,n,p}，都有S(u)=S(v)=\{\mathrm{1,2},\cdots ,\Delta +\mathrm{1}\}。故该染色为K_{m,n,p}的一个点可约全染色，且{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=\Delta +\mathrm{1}。

情形4.2 若{\chi }^{\text{'}}(K_{m,n,p})=\Delta +\mathrm{1}，则说明K_{m,n,p}用\Delta +\mathrm{1}种色正常边染色时，每个点的色集合恰好缺\mathrm{2}m+\mathrm{1}种色的一种，将每个点所缺的这种色对应染在顶点上。此时得到的正常全染色满足\forall u,v\in K_{m,n,p}，都有S(u)=S(v)=\{\mathrm{1,2},\cdots ,\Delta +\mathrm{1}\}，故该染色为K_{m,n,p}的一个点可约全染色，且{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=\Delta +\mathrm{1}。

综上可知，{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(K_{m,n,p})=\Delta +\mathrm{1}。

注：根据上述情形\mathrm{4}的证明，类似可以得到对任意完全等部图G，有{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(G)=\Delta (G)+\mathrm{1}。

3　 结 语

本文在点可约边染色和点可约全染色概念的基础上，运用图的色集合事先分配法、组合分析法和构造染色法，结合完美匹配探讨了完全三部图K_{m,n,p}的点可约全染色问题，进一步确定了K_{m,n,p}的点可约全色数。并得到了对任意完全等部图G，有{\chi }_{\mathrm{v}\mathrm{r}\mathrm{t}}(G)=\Delta (G)+\mathrm{1}的推论。从完全k部图的结构来看，k值越大，对其进行点可约全染色也就越困难。目前已经得到了完全二部图、完全三部图以及完全等部图的点可约全色数，关于完全k部图\left(k\ge \mathrm{4}\right)的点可约全染色还需要进一步深入研究。

参考文献

[1] ZHANG Z F， LIU L Z， WANG J F. Adjacent strong edge coloring of graphs ［J］. Applied Mathematics Letters， 2002， 15（5）： 623-626. DOI： 10.1016/S0893-9659 （02） 80015-5 .

[2] 李沐春，王立丽，张伟东，等. 若干类3-正则图的 S m a r a n d a c h e l y 邻点全染色的界［J］.南开大学学报（自然科学版），2014，47（6）：79-84. DOI： CNKI：SUN：NKDZ.0.2014- 06-014 .

[3] LI M C， WANG L L， ZHANG W D，et al. Bounds on S m a r a n d a c h e l y adjacent vertex total-coloring of some classes of 3-regular graphs ［J］. Acta Scientiarum Naturalium Universitatis Nankaiensis，2014，47（6） ：79-84. DOI： CNKI：SUN：NKDZ.0.2014-06-014（Ch ）.

[4] 李沐春，文飞，张荔. 图 K 2 n + 1 \ E K 2 , m 的点可区别全染色［J］. 南开大学学报（自然科学版）， 2012， 45（6）： 59-65.

[5] LI M C， WEN F， ZHANG L. Vertex distinguishing total-coloring of graph K 2 n + 1 \ E K 2 , m ［J］. Acta Scientiarum Naturalium Universitatis Nankaiensis，2012，45（6）：59-65 （Ch）.

[6] LI J W， ZHANG Z F， ZHU E Q， et al. Adjacent vertex reducible edge-total coloring of graphs ［C］// 2009 2nd International Conference on BioMedical Engineering and Informatics. New York： IEEE Press， 2009： 1-3.DOI：10.1109/BMEI. 2009.5304740 .

[7] 朱恩强. 若干图类的新染色问题［D］. 兰州：兰州交通大学， 2010.

[8] ZHU E Q. The New Coloring Problems of Some Graphs ［D］. Lanzhou：Lanzhou Jiaotong University，2010 （Ch）.

[9] 张园萍，强会英，孙亮萍. 星扇轮联图的邻点可约边染色［J］. 数学的实践与认识， 2012， 42（13）： 207-213. DOI： 10.3969/j.issn.1000-0984.2012.13.030 .

[10] ZHANG Y P， QIANG H Y， SUN L P. Adjacent reducible edge cloring of star fan wheel of join-graphs ［J］. Mathematical Practice And Cognition， 2012， 42（13）： 207-213. DOI： 10.3969/j.issn.1000-0984.2012.13.030（Ch ）.

[11] 陈祥恩，张爽.图 K 2,3 , p 的点可区别IE-全染色及一般全染色［J］.西北师范大学学报（自然科学版），2020，56（3）：7-13+30.DOI：10.16783/j.cnki.nwnuz.2020.03.002 .

[12] CHEN X E， ZHANG S. Vertex distinguishing IE-total coloring and general total coloring of graph K 2,3 , p ［J］. Journal of Northwest Normal University （Natural Science），2020，56（3）：7-13+30. DOI：10.16783/j.cnki.nwnuz.2020.03.002（Ch ）.

[13] 杨佳睿，陈祥恩. K 3,3 , p 的点可区别的一般全染色［J］.山东大学学报（理学版），2021，56（1）：18-23.

[14] YANG J R， CHEN X E.Vertex-distinguishing general total coloring of K 3,3 , p ［J］. Journal of Shandong University（Natural Science），2021，56（1）：18-23 （Ch）.

[15] 李敬文，康玉梅，张树成，等.图的点和可约边染色［J］. 武汉大学学报（理学版），2022，68（5）：578-596. DOI：10.14188/j.1671-8836.2020.0314 .

[16] LI J W， KANG Y M， ZHANG S C，et al. The vertex sum reducible edge coloring for graphs［J］. J Wuhan Univ（Nat Sci Ed），2022，68（5）：578-596. DOI：10.14188/j.1671-8836.2020.0314（Ch ）.

[17] BONDY J A， MURTY U S R. Graph Theory with Applications ［M］. New York： Palgrave， 1976. DOI： 10.1007/978-1-349-03521-2 .

基金资助

国家自然科学基金(11961041)

甘肃省自然科学基金(21JR11RA065)