图的点和可约边染色

The Vertex Sum Reducible Edge Coloring for Graphs

摘要

在已有图染色概念基础之上，结合实际问题提出了点和可约边染色的概念，设计了一种新型的点和可约边染色（vertex sum reducible edge coloring）算法，该算法使用逐步趋向最优解方法对随机图的染色进行研究。通过对实验结果进行分析，得到了若干定理及证明。

Abstract

Based on the existing concept of graph coloring and combined with practical problems, the concept of vertex sum reducible edge coloring is proposed, and a novel vertex sum reducible edge coloring algorithm is designed, which uses a stepwise approach to the optimal solution method to study the coloring of random graphs. Through the analysis of experimental results, several theorems and proofs are obtained.

Graphical abstract

关键词

图 / 算法 / 点和可约边染色 / 点和可约边色数

Key words

graphs / algorithm / vertex sum reducible edge coloring / vertex sum reducible edge chromatic number

0　 引 言

图染色问题一直是图论中的一个经典课题，许多学者围绕它进行了一系列的研究探索。近年来随着信息技术的发展，多种新的染色概念也被相继提出，如可区别染色、点和可区别染色以及点可约染色等^［1~7］。1997年，Burris和Schelp^［7］提出了点可区别边染色的概念和相关猜想，随后文献［8，9］对可区别染色进行了进一步的研究和探讨。2009年，文献［10］在可区别染色的理论基础上提出了一系列图的可约染色概念。2010年，Chartrand等^［11］通过对图与网络的非正则强度研究，正式开启了对图的色和可区别染色研究。2013年，Flandrin等^［12］通过研究邻和可区别边染色提出了邻和可区别边染色猜想。2015年，Pilśniak等^［13］提出了图的邻和可区别全染色的概念及猜想。

基于上述所提到的染色概念，本文提出了一种新染色——点和可约边染色。通过借鉴传统的遗传算法、蚁群算法、模拟退火算法等智能算法的核心思想，设计了一种新型的点和可约边染色算法，得到了19点以内的树图、路图、圈图、星图、风筝图、友谊图以及这些特殊图组合得到的联图的结果。最后通过对实验结果的分析，给出若干定理及证明。

1　 基础知识

定义1 设G(V,E)是一个简单图，d(u)表示顶点u的度，S(u)表示顶点u的染色和。若存在正整数k(\mathrm{1}\le k\le |E|)和映射f:E(G)\to \{\mathrm{1,2},\dots ,k\}，使得对任意两点u,v\in V(G)，当d(u)=d(v)时，S(u)=S(v)，其中S(u)=\sum _{uv\in E(G)}f(uv)，则称f为G的点和可约边染色（vertex sum reducible edge coloring，简称k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}），且{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(G)=\mathrm{m}\mathrm{a}\mathrm{x}\{k|k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C} of G\}为点和可约边色数。显然{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(G)是存在的。

定义2 设图G_n的顶点集为\{u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n\}，图H_m的顶点集为\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_m\}。如果G_n和H_m有中心节点，分别用u_{\mathrm{1}}和v_{\mathrm{1}}表示，G_n\uparrow H_m表示将H_m的中心节点v_{\mathrm{1}}连接到G_n的任意一个顶点后得到的图，则有

V(G_n\uparrow H_m)=V(G_n)\bigcup V(H_m)

E(G_n\uparrow H_m)=E(G_n)\bigcup E(H_m)

V(G_n\uparrow H_m)=|V(G_n)|+|V(H_m)|-v_{\mathrm{1}}

E(G_n\uparrow H_m)=\left|E(G_n)\right|+\left|E(H_m)\right|

图1为G_n\uparrow H_m图示例，其中（a）是顶点数为n的圈图C_n和星图S_{\mathrm{5}}连接得到的联图，（b）为圈图C_n和圈图C_m连接得到的联图。

定义3^［6］ 风筝图（\mathrm{K}\mathrm{i}\mathrm{t}\mathrm{e}）：(n,t)⁃K是圈图C_n中任意顶点与长度为t路图P_t端点相连接的图。

引理1 对于简单图G，当{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(G)=k存在而{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(G)=k+\mathrm{1}不存在时，图G的点和可约边色数即为k。

根据定义1，引理1显然成立。

2　 VSREC算法

根据点和可约边染色的定义，本文提出了VSREC算法，通过调整算子逐步破坏平衡，再利用平衡算子建立平衡，慢慢地趋向最优解，完成对图的染色过程。

2.1　算子设计

1） 调整算子

当达到某次染色平衡但没有满足图的边数或者下次操作无效时，就需要调整参数，打破当前平衡，使其达到下一次平衡。在调整参数过程中，应当遵循的原则是：

① 选择最多的染色数调整；

② 选择度相同的顶点，然后根据平衡参数修改当前色数。

具体步骤如下：

① 判断更新的平衡染色矩阵{\mathit{M}}_i是否得到最大色数q且平衡或者{\mathit{M}}_i={\mathit{M}}_{i+\mathrm{1}}？若是，输出该染色矩阵；若否，则转②继续执行。

② 根据当前平衡染色矩阵{\mathit{M}}_i，从左到右，从上到下，依次调整参数（注：算法执行过程中对染色矩阵的上三角进行调整，之后对下三角值进行相应的修改）。

③ 判断是否满足k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}？满足，转②继续执行算法。否则，转④执行。

④ 跳出当前循环，对外层循环下一个不为0的边色数进行染色，继续执行②。

2） 平衡算子

具体步骤如下：

① 从平衡染色矩阵{\mathit{M}}_i中得到边集合E_i，进入调整算子。

② 用count进行标识，初始化\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}=\mathrm{0}，根据平衡参数，改变边集合E_{\mathrm{1}}中的色数，得到边集合E_i(i=\mathrm{2,3},\dots ,q)，同时，count=count+1。判断同度点的色和不超过2或者矩阵中色数是否连续？若满足，则转②继续循环；若不满足，则退回count=count-1的状态，进入调整算子。

③ 达到一次平衡状态，就用当前平衡状态矩阵{\mathit{M}}_i重新记录一下，直到\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}=\mathrm{0}。

2.2　VSREC算法流程

VSREC算法流程如下。

友谊图T_{(\mathrm{2,3})}是利用VSREC算法得到的，过程如图2。图3为染色后的示例。图2示例的最终平衡状态M_{\mathrm{6}}=\{E_{\mathrm{1}},E_{\mathrm{2}},E_{\mathrm{3}},E₄，E_{\mathrm{5}},E_{\mathrm{6}}\}。其中，E_{\mathrm{1}}=\{(\mathrm{6,7})\}；E_{\mathrm{2}}=\{(\mathrm{4,5})\}；E_{\mathrm{3}}=\{(\mathrm{1,3})(\mathrm{2,3})\}；E_{\mathrm{4}}=\{(\mathrm{1,2})\}；E_{\mathrm{5}}=\{(\mathrm{3,4})(\mathrm{3,5})\}；E_{\mathrm{6}}=\{(\mathrm{3,6})(\mathrm{3,7})\}。

3　 定理及证明

定理1 若P_n是含n(n\ge \mathrm{2})个顶点的一条路，则

{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(P_n)=\left\{\begin{array}{ll}\mathrm{1},& n=\mathrm{2}\mathrm{a}\mathrm{n}\mathrm{d}n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{2},& n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

定理2 设S_n是含n+\mathrm{1}(n>\mathrm{2})个顶点的星图，则{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(S_n)=\mathrm{1}。

定理3 设C_n是含n(n\ge \mathrm{3})个顶点的圈图，则

{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n)=\left\{\begin{array}{cc}\mathrm{1},& n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{2},& n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

根据k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}定义和路、星、圈图的特性，上述定理1~3显然都成立。

定理4 对于联图C_n\uparrow H(n\ge \mathrm{3}),存在

{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow H)=\left\{\begin{array}{c}\mathrm{3},H(S_m)\\ \mathrm{4},H(P_m)\end{array}\right.，m\ge \mathrm{2}

证 1） 设C_n的点集为V=\{u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n\}，S_m的点集为V=\{v_{\mathrm{0}},v_{\mathrm{1}},\dots ,v_m\}，其中u_{\mathrm{1}}=v_{\mathrm{0}}。

图C_n\uparrow S_m满足f染色，

\begin{array}{l}f(u_i{u}_{i+\mathrm{1}})=\left\{\begin{array}{cc}\mathrm{2},& i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{1},& i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,n-\mathrm{1}\end{array}；

f(v_{\mathrm{0}}{v}_i)=\mathrm{3},i=\mathrm{1,2},\dots ,m

证得{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow S_m)\ge \mathrm{3}。已知C_n\uparrow S_m存在1个最大度顶点，m个1度顶点和n-\mathrm{1}个2度顶点。根据k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}定义，C_n\uparrow S_m中m个1度顶点的色和必须相同，n-\mathrm{1}个2度顶点色和必须相同。

假设{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow S_m)=\mathrm{4}时，令与1度顶点或者与2度顶点关联的任意一条边染色数为4，如f(v_{\mathrm{0}}{v}_{\mathrm{1}})=\mathrm{4}，此时，至少存在一个1度顶点v_{\mathrm{1}}与m-\mathrm{1}个1度顶点v_i(i=\mathrm{2,3},\dots ,m)的色和不同。这与假设矛盾。故根据引理1，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow S_m)=\mathrm{3}。

2） 设(n,t)⁃K图点集为V=V(C_n)\bigcup V(P_m)=\{u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n,v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_m\}，其中u_{\mathrm{1}}=v_{\mathrm{1}}。

① 当n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，(n,t)⁃K满足f染色

\begin{array}{l}f(u_i{u}_{i+\mathrm{1}})=\left\{\begin{array}{cc}\mathrm{4},& i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{1},& i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,n-\mathrm{1}\end{array}

f(u_n{u}_{\mathrm{1}})=\mathrm{1}；

\begin{array}{l}f(v_i{v}_{i+\mathrm{1}})=\left\{\begin{array}{cc}\mathrm{3},& i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{2},& i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,m-\mathrm{1}\end{array}

② 当n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}((n,t)⁃K）满足f染色，

\begin{array}{l}f(u_i{u}_{i+\mathrm{1}})=\left\{\begin{array}{cc}\mathrm{4},& i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{1},& i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,n-\mathrm{1}\end{array}

f(u_n{u}_{\mathrm{1}})=\mathrm{4}；

f(v_i{v}_{i+\mathrm{1}})=\left\{\begin{array}{cc}\mathrm{2},& i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{3},& i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

i=\mathrm{1,2},\dots ,m-\mathrm{1}

证得{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}((n,t)⁃K)\ge \mathrm{4}。已知(n,t)⁃K存在1个3度顶点，1个1度顶点和m+n-\mathrm{2}个2度顶点。根据k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}定义，(n,t)⁃K中所有2度顶点色和必须相同。

同样，假设{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}((n,t)⁃K)=\mathrm{5}时，令与2度顶点关联的任意一条边染色数为5。(n,t)⁃K至少存在一个2度顶点的色和S(u)不同于其余2度顶点的色和。与假设矛盾。故根据引理1，当n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}((n,t)⁃K)=\mathrm{4}。

显然(n,t)⁃K图的{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}((n,t)⁃K)=\mathrm{4}。

3） 如图4所示为(n,t)⁃K图的部分染色示例。

猜测1 对树图T_n(n\ge \mathrm{3})，\mathrm{1}\le {\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_n)\le l（l为树T_n的层数）。

证 1） 根据VSREC算法，得到19个点树图的染色结果，如表1所示。

2） 根据树图T_n性质，已知每棵树图T_n的层数l是不确定的。为此，以树图T_n的最大度为树根构造具有唯一层数l的树。分两种情况：

① 若T_n具有唯一最大度，则以最大度为树根构造树。

② 若T_n具有多个最大度，则以最大度构造树的层数l最大的一个最大度为树根。

3） 根据上述2）得到树图T_n的层数l：

\mathrm{2}\le l\le n-\mathrm{1}

故从表1得出，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_n)\le n-\mathrm{1}恒成立。

4） 图5给出最大色数的树图T_n情况。对其进行分析验证，得出当\mathrm{3}\le n\le \mathrm{19}时，

{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_n)\le l

5） 从上述1）~4）分析得到：对树图T_n(\mathrm{3}\le n\le \mathrm{19})，l是以最大度确定的树T_n的层数，则\mathrm{1}\le {\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_n)\le l。进一步验证了猜测1的结论。

定理5 对友谊图T_{(\mathrm{2},n)}(n\ge \mathrm{1})，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)})=\Delta。

证 1） 友谊图T_{(\mathrm{2},n)}(n\ge \mathrm{1})表示n个C_{\mathrm{3}}图组成的图，如图6所示。

2） 根据k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}定义和T_{(\mathrm{2},n)}(n\ge \mathrm{1})图得到染色：

f(u_i{v}_i)=i,i=\mathrm{1,2},\dots ,n

\begin{array}{l}f(u_{\mathrm{0}}{u}_i)=f(u_{\mathrm{0}}{v}_i)=\mathrm{2}n-i+\mathrm{1},\\ i=\mathrm{1,2},\dots ,n\end{array}

此时，证得{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)})\ge \mathrm{2}n。又可知友谊图T_{(\mathrm{2},n)}只存在一个最大度顶点和2n个2度顶点。根据k⁃VSREC定义，T_{(\mathrm{2},n)}图中所有2度顶点色和必须相同。

假设当{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)})=\mathrm{2}n+\mathrm{1}时，令与2度顶点关联的任意一条边染色数为\mathrm{2}n+\mathrm{1}。如令f(u_{\mathrm{1}}{v}_{\mathrm{1}})=\mathrm{2}n+\mathrm{1}，则至少存在一个2度顶点u_{\mathrm{1}}的色和S(u)不同于2度顶点v_i,u_i(i=\mathrm{2,3},\dots ,n)的色和。与假设矛盾。

故根据引理1证得T_{(\mathrm{2},n)}(n\ge \mathrm{1})图存在{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)})=\mathrm{2}n，又因T_{(\mathrm{2},n)}(n\ge \mathrm{1})图的\Delta =\mathrm{2}n。即{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)})=\Delta。

3） 根据VSREC算法执行结果，图7显示了友谊图T_{(\mathrm{2},n)}中n与{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_n)的关系，图8为n\ge \mathrm{19}的T_{(\mathrm{2},n)}图的部分结果示例。

定理6 对于联图T_{(m,n)}(n\ge \mathrm{1},m\ge \mathrm{2})，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(m,n)})=\Delta。

证 1） 联图T_{(m,n)}(n\ge \mathrm{1},m\ge \mathrm{2})表示n个C_{m+\mathrm{1}}圈图连接的图，如图9所示。

2） 设T_{(m,n)}的点集合为\{u_{\mathrm{0}},u_{\mathrm{1}}^{\mathrm{1}\mathrm{\text{'}}},\dots ,u_{\mathrm{1}}^{m^{\mathrm{\text{'}}}},u_{\mathrm{2}}^{\mathrm{1}\mathrm{\text{'}}},\dots ,u_{\mathrm{2}}^{m^{\mathrm{\text{'}}}},\dots ,u_n^{\mathrm{1}\mathrm{\text{'}}},\dots ,u_n^{m^{\mathrm{\text{'}}}}\}。利用VSREC算法得到的结果和定理6推导可得T_{(m,n)}满足f染色，

f(u_{\mathrm{0}}{u}_i^{\mathrm{1}\mathrm{\text{'}}})=i,i=\mathrm{1,2},\dots ,n

\begin{array}{l}f(u_{\mathrm{0}}{u}_i^{m\mathrm{\text{'}}})=\left\{\begin{array}{ll}i,& m=\mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{2}n+\mathrm{1}-i,& m=\mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,n\end{array}

\begin{array}{l}f(u_i^{j\mathrm{\text{'}}}{u}_i^{(j+\mathrm{1})\mathrm{\text{'}}})=\left\{\begin{array}{ll}i,& j\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{2}n+\mathrm{1}-i,& j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,n;j=\mathrm{1,2},\dots ,m-\mathrm{1}\end{array}

此时，证得{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(m,n)})\ge \mathrm{2}n。又可知联图T_{(m,n)}只存在一个最大度顶点和m\timesn个2度顶点。根据k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}定义，T_{(m,n)}图中所有2度顶点色和必须相同。

当{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(m,n)})=\mathrm{2}n+\mathrm{1}时，令T_{(m,n)}图中任意一条边的染色数为\mathrm{2}n+\mathrm{1}，那么至少存在一个2度顶点的色和不同于其余2度顶点的色和。这与假设矛盾。故根据引理1，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(m,n)})=\mathrm{2}n，又因T_{(m,n)}(n\ge \mathrm{1},m\ge \mathrm{3})图的\Delta =\mathrm{2}n。即{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(m,n)})=\Delta。

定理7 对联图T_{(\mathrm{2},n)}\uparrow H，

{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{\left(\mathrm{2},n\right)}\uparrow H)=\left\{\begin{array}{ll}\mathrm{2}n+\mathrm{1},& n\ge \mathrm{1},m\ge \mathrm{2}\mathrm{a}\mathrm{n}\mathrm{d}H(S_m)\\ \Delta +\mathrm{1},& n\ge \mathrm{1},m\ge \mathrm{2}\mathrm{a}\mathrm{n}\mathrm{d}H(P_m)\\ \Delta ,& n\ge \mathrm{1},m\ge \mathrm{3}\mathrm{a}\mathrm{n}\mathrm{d}H(C_m)\end{array}\right.

证 联图T_{(\mathrm{2},n)}\uparrow H如图10所示。

根据定理5可得联图T_{(\mathrm{2},n)}\uparrow H，证明如下：

1） 当H为P_m(m\ge \mathrm{2})时，T_{(\mathrm{2},n)}\uparrow P_m如图9（a）所示。

T_{(\mathrm{2},n)}\uparrow P_m满足f染色，

f(u_i{v}_i)=i,i=\mathrm{1,2},\dots ,n

f(u_i{v}_i)=f(u_{\mathrm{0}}{v}_i)=(\mathrm{2}n+\mathrm{3})-i,i=\mathrm{1,2},\dots ,n

f(w_i{w}_{i+\mathrm{1}})=\left\{\begin{array}{c}n+\mathrm{2},m\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ n+\mathrm{1},m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

i=\mathrm{0,1},\mathrm{2},\dots ,m

证得{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)}\uparrow P_m)\ge \mathrm{2}n+\mathrm{1}。已知联图T_{(\mathrm{2},n)}\uparrow P_m存在一个最大度顶点，1个1度顶点和\mathrm{2}n+m-\mathrm{1}个2度顶点。根据k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}定义，T_{(\mathrm{2},n)}\uparrow P_m图中所有2度顶点色和必须相同。

假设{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)}\uparrow P_m)=\mathrm{2}n+\mathrm{2}，令T_{(\mathrm{2},n)}\uparrow P_m图中与2度顶点关联的任意一条边染色数为\mathrm{2}n+\mathrm{2}，那么至少存在一个2度顶点的色和不同于其余2n+m个2度顶点的色和。这与假设矛盾。故根据引理1，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)}\uparrow P_m)=\mathrm{2}n+\mathrm{1}。

又因T_{(\mathrm{2},n)}\uparrow P_m图的\Delta =\mathrm{2}n+\mathrm{1}。故{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)}\uparrow P_m)=\Delta +\mathrm{1}。

2） 当H为S_m(m\ge \mathrm{2})时，T_{(\mathrm{2},n)}\uparrow S_m如图9（b）所示。

同理，T_{(\mathrm{2},n)}\uparrow S_m满足f染色，

f(u_i{v}_i)=i,i=\mathrm{1,2},\dots ,n

f(u_{\mathrm{0}}{u}_i)=f(u_{\mathrm{0}}{v}_i)=\mathrm{2}n-i+\mathrm{1}(i=\mathrm{1,2},\dots ,n)

f(w_{\mathrm{0}}{w}_i)=\mathrm{2}n+\mathrm{1},i=\mathrm{1,2},\dots ,m

证得{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)}\uparrow S_m)\ge \mathrm{2}n+\mathrm{1}。已知T_{(\mathrm{2},n)}\uparrow S_m存在1个最大度顶点，m个1度顶点和2n个2度顶点。根据k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}定义，C_n\uparrow S_m中m个1度顶点的色和必须相同，2n个2度顶点的色和必须相同。

假设{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{\left(\mathrm{2},n\right)}\uparrow S_m)=\mathrm{2}n+\mathrm{2}，令与1度顶点或者与2度顶点关联的任意一条边染色数为2n+2，如f(w_{\mathrm{0}}{w}_{\mathrm{1}})=\mathrm{2}n+\mathrm{2}，此时，至少存在一个1度顶点w_{\mathrm{1}}与m-1个1度顶点w_i(i=\mathrm{2,3},\dots,m)的色和不同。这与假设矛盾。故根据引理1，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)}\uparrow S_m)=\mathrm{2}n+\mathrm{1}。

3） 当H为C_m(m\ge \mathrm{3})时，设T_{(\mathrm{2},n)}的顶点集为\{u_{\mathrm{0}},u_{\mathrm{1}},v_{\mathrm{1}},u_{\mathrm{2}},v_{\mathrm{2}},\dots ,u_n,v_n\}，C_m的顶点集为\{w_{\mathrm{0}},w_{\mathrm{1}},w_{\mathrm{2}},\dots ,w_m\}，其中u_{\mathrm{0}}=w_{\mathrm{0}}=w_m。

T_{(\mathrm{2},n)}\uparrow C_m满足f染色，

f(u_i{v}_i)=i,i=\mathrm{1,2},\dots ,n

f(u_{\mathrm{0}}{u}_i)=f(u_{\mathrm{0}}{v}_i)=\mathrm{2}n+\mathrm{1}-i,i=\mathrm{1,2},\dots ,n

f(w_{\mathrm{0}}{w}_{\mathrm{1}})=n+\mathrm{1}

\begin{array}{l}f(w_i{w}_{i+\mathrm{1}})=\left\{\begin{array}{cc}n+\mathrm{1},& i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ n,& i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,m-\mathrm{1}\end{array}

证得{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)}\uparrow C_m)\ge \mathrm{2}n。已知T_{(\mathrm{2},n)}\uparrow C_m存在1个最大度顶点和\mathrm{2}n+m-\mathrm{1}个2度顶点。根据k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}定义，T_{(\mathrm{2},n)}\uparrow C_m中\mathrm{2}n+m-\mathrm{1}个2度顶点色和必须相同。

假设{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)}\uparrow C_m)=\mathrm{2}n+\mathrm{1}，令与2度顶点关联的任意一条边染色数为\mathrm{2}n+\mathrm{1}。如使f(w_{\mathrm{0}}{w}_{\mathrm{1}})=\mathrm{2}n+\mathrm{1}，即当f(w_{\mathrm{0}}{w}_{\mathrm{1}})=\mathrm{2}n+\mathrm{1}时，至少存在一个2度顶点w_{\mathrm{1}}的色和S(u)不同于其余\mathrm{2}n+m个2度顶点的色和。与假设矛盾。故根据引理1，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)}\uparrow C_m)=\mathrm{2}n，又因T_{(\mathrm{2},n)}\uparrow C_m(n\ge \mathrm{1},m\ge \mathrm{3})图的\Delta =\mathrm{2}n。即{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(T_{(\mathrm{2},n)}\uparrow C_m)=\Delta得证。

综上所述，定理7成立。

利用VSREC算法，得到T_{(\mathrm{2},n)}\uparrow H(P_m,S_m,C_m)的部分结果，如图11所示。

定理8 对联图C_n\uparrow P_m\uparrow C_n(n\ge \mathrm{3},m\ge \mathrm{1})，存在

{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow P_m\uparrow C_n)=\left\{\begin{array}{cc}\mathrm{5},& n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),m\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{6},& n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{4},& n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),m\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{3},& n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.

证 1） C_n\uparrow P_m\uparrow C_n如图12所示。

2） 当n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),m\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，图C_n\uparrowP_m\uparrow C_n满足f染色

\begin{array}{l}f(u_i{u}_{i+\mathrm{1}})=f(u_i^{\mathrm{\text{'}}}{u}_{i+\mathrm{1}}^{\mathrm{\text{'}}})=\left\{\begin{array}{cc}\mathrm{4},& i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{1},& i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,n-\mathrm{1}\end{array}；

\begin{array}{l}f(v_i{v}_{i+\mathrm{1}})=\left\{\begin{array}{cc}\mathrm{2},& i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{3},& i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{2},\dots ,m-\mathrm{1}\end{array}

f(u_n{u}_{\mathrm{1}})=\mathrm{1}，f(u_n^{\mathrm{\text{'}}}{u}_{\mathrm{1}}^{\mathrm{\text{'}}})=\mathrm{1}

证得{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow P_m\uparrow C_n)\ge \mathrm{4}。已知C_n\uparrow P_m\uparrow C_n存在2个3度顶点和\mathrm{2}n+m-\mathrm{4}个2度顶点。根据k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}定义，C_n\uparrow P_m\uparrow C_n中\mathrm{2}n+m-\mathrm{4}个2度顶点色和必须相同。

设{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow P_m\uparrow C_n)=\mathrm{5}，令C_n\uparrow P_m\uparrow C_n图中任意一条边染色数为5，如令f(u_{\mathrm{1}}{u}_{\mathrm{2}})=\mathrm{5}时，至少存在一个2度顶点u_{\mathrm{2}}的色和不同于其余\mathrm{2}n+m-\mathrm{3}个2度顶点的色和。不满足k⁃\mathrm{V}\mathrm{S}\mathrm{R}\mathrm{E}\mathrm{C}的定义且与假设矛盾。故根据引理1，当n\equiv \mathrm{1}，m\equiv\mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow P_m\uparrow C_n)=\mathrm{4}。

3） 当n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，图C_n\uparrowP_m\uparrow C_n满足f染色，

\begin{array}{l}f(u_i{u}_{i+\mathrm{1}})=f(u_i^{\mathrm{\text{'}}}{u}_{i+\mathrm{1}}^{\mathrm{\text{'}}})=\left\{\begin{array}{c}\mathrm{3},i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{1},i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,n-\mathrm{1}\end{array}；

f(v_i{v}_{i+\mathrm{1}})=\mathrm{2},i=\mathrm{2},\dots ,m-\mathrm{1}；

f(u_n{u}_{\mathrm{1}})=\mathrm{1}，f(u_n^{\mathrm{\text{'}}}{u}_{\mathrm{1}}^{\mathrm{\text{'}}})=\mathrm{1}

此时，证得{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow P_m\uparrow C_n)\ge \mathrm{3}。已知C_n\uparrow P_m\uparrow C_n存在2个3度顶点和\mathrm{2}n+m-\mathrm{4}个2度顶点。根据k⁃VSREC定义，C_n\uparrow P_m\uparrow C_n中\mathrm{2}n+m-\mathrm{4}个2度顶点色和必须相同。

设{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow P_m\uparrow C_n)=\mathrm{4}，令C_n\uparrow P_m\uparrow C_n图中任意一条边染色数为5，如令f(u_{\mathrm{1}}{u}_{\mathrm{2}})=\mathrm{4}时，也至少存在一个2度顶点u_{\mathrm{2}}的色和不同于其余\mathrm{2}n+m-\mathrm{3}个2度顶点的色和。与假设矛盾。根据引理1，当n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow P_m\uparrowC_n)=\mathrm{3}。

4） 当n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，图C_n\uparrowP_m\uparrow C_n满足f染色，

\begin{array}{l}f(u_i{u}_{i+\mathrm{1}})=\left\{\begin{array}{c}\mathrm{6},i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{1},i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,n-\mathrm{1}\end{array}；

\begin{array}{l}f(u_i^{\mathrm{\text{'}}}{u}_{i+\mathrm{1}}^{\mathrm{\text{'}}})=\left\{\begin{array}{c}\mathrm{5},i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{2},i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,n-\mathrm{1}\end{array}；

\begin{array}{l}f(v_i{v}_{i+\mathrm{1}})=\left\{\begin{array}{c}\mathrm{4},i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{3},i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,m-\mathrm{1}\end{array}；

f(u_n{u}_{\mathrm{1}})=\mathrm{6}，f(u_n^{\mathrm{\text{'}}}{u}_{\mathrm{1}}^{\mathrm{\text{'}}})=\mathrm{5}

同理，证得{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow P_m\uparrow C_n)=\mathrm{6}。

5） 当n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),m\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，图C_n\uparrow P_m\uparrow C_n满足f染色，

\begin{array}{l}f(u_i{u}_{i+\mathrm{1}})=\left\{\begin{array}{c}\mathrm{5},i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{1},i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,n-\mathrm{1}\end{array}；

\begin{array}{l}f(u_i^{\mathrm{\text{'}}}{u}_{i+\mathrm{1}}^{\mathrm{\text{'}}})=\left\{\begin{array}{c}\mathrm{4},i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ \mathrm{2},i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.\\ i=\mathrm{1,2},\dots ,n-\mathrm{1}\end{array}；

f(v_i{v}_{i+\mathrm{1}})=\mathrm{3},i=\mathrm{1,2},\dots ,m-\mathrm{1}；

f(u_n{u}_{\mathrm{1}})=\mathrm{5}，f(u_n^{\mathrm{\text{'}}}{u}_{\mathrm{1}}^{\mathrm{\text{'}}})=\mathrm{4}

设{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow P_m\uparrow C_n)=\mathrm{6}时，同理证得联图C_n\uparrow P_m\uparrow C_n至少存在一个2度顶点u_{\mathrm{2}}的色和不同于其余\mathrm{2}n+m-\mathrm{3}顶点的色和。这与假设矛盾。故根据引理1，当n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),m\equiv\mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})时，{\chi }_{\mathrm{v}\mathrm{s}\mathrm{r}}^{\mathrm{\text{'}}}(C_n\uparrow P_m\uparrow C_n)=\mathrm{5}。

综上所述，定理8成立。

4　 结 语

本文在已有图染色概念基础之上，提出了图的点和可约边染色新概念，针对该染色设计了一种新的VSREC算法，使用算法对路、圈、星等特殊图以及随机图的染色进行研究，给出了8个定理及证明和1个猜测。从算法效率看，VSREC算法可以快速完成大点数图集的染色，但并不能保证每次染色得到的都为最优解，之后仍需要对其进行优化和改进。从算法结果看，目前只对特殊图和一小部分联图进行了结果分析，关于大量随机图的点和可约边染色需要进一步的深入研究。

参考文献

[1] BURRIS A C， SCHELP R H. Vertex-distinguishing proper edge-colorings ［J］. Journal of Graph Theory， 1997， 26（2）： 73-82. DOI：10.1002/（sici）1097-0118（199710）26： 273： aid-jgt2>3.0.co；2-c .

[2] BAZGAN C， HARKAT-BENHAMDINE A， LI H， et al. On the vertex-distinguishing proper edge-colorings of graphs ［J］. Journal of Combinatorial Theory， Series B， 1999， 75（2）： 288-301. DOI：10.1006/jctb.1998.1884 .

[3] BALISTER P N， BOLLOBÁS B， SCHELP R H. Vertex distinguishing colorings of graphs with Δ（G）=2 ［J］. Discrete Mathematics， 2002， 252（1/2/3）： 17-29. DOI：10.1016/S0012-365X（01）00287-4 .

[4] 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 .

[5] GYŐRI E， HORŇÁK M， PALMER C， et al. General neighbour-distinguishing index of a graph ［J］. Discrete Mathematics， 2008， 308（5/6）： 827-831. DOI：10.1016/j.disc.2007.07.046 .

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

[7] BURRIS A C， SCHELP R H. Vertex-distinguishing proper edge-colorings ［J］. Journal of Graph Theory， 1997，26（2）： 73-82. DOI：10.1002/（sici）1097-0118（199710）26：2<73：：aid-jgt2>3.0.co；2-c .

[8] BALISTER P N， RIORDAN O M， SCHELP R H. Vertex⁃distinguishing edge colorings of graphs ［J］. Graph Theory， 2003，42（2）：95-109. DOI：10.1002/jgt.10076 .

[9] ZHU E Q， ZHANG Z F， WANG Z W，et al. Adjacent vetex reducible vertex-total coloring of graphs ［DB/OL］. ［2020-01-02］.DOI： 10.1109/CISE.2009.5365082 .

[10] 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 .

[11] CHARTRAND G， JOHNS G L， MCKEON K A， et al. The rainbow connectivity of a graph ［J］. Networks， 2010， 54（2）：75-81. DOI：10.1002/net.20296 .

[12] FLANDRIN E， MARCZYK A， PRZYBYŁO J， et al. Neighbor sum distinguishing index ［J］. Graphs and Combinatorics， 2013， 29（5）： 1329-1336. DOI：10.1007/s00373-012-1191-x .

[13] PILŚNIAK M， WOŹNIAK M. On the total-neighbor-distinguishing index by sums ［J］. Graphs and Combinatorics， 2015， 31（3）： 771-782. DOI：10.1007/s00373-013-1399-4 .

基金资助

国家自然科学基金资助项目(11961041)

国家自然科学基金资助项目(62062049)

国家自然科学基金资助项目(11461038)