彩虹不连通染色数

Rainbow Disconnection Coloring Number

摘要: 设G是一个非平凡的边染色连通图，如果图G的一个边割R中没有任何两条边是相同的颜色，则称R是图G的一个彩虹边割。u和v是图G的任意两个不相同的顶点，如果图G的一个彩虹边割R满足u和v属于$G-R$ 的不同连通分支，则称图G的这个边染色为彩虹不连通染色。本文主要对图的彩虹不连通染色已有的结论进行综述，并讨论了一些结论之间的关系。

Abstract: Let G be a nontrivial connected, edge-colored graph, and an edge-cut R of G is called a rainbow cut if no two edges in R are colored the same. An edge-coloring of G is a rainbow disconnection coloring if for every two distinct vertices u and v of G, there exists a rainbow cut in G, where u and v belong to different components of $G-R$ . In this paper, we summerize the results for rainbow disconnection colorings in graph, and the relationship between some conclusions is discussed.

1. 引言

经典的染色理论是图论学科中的一个非常重要而且比较活跃的研究领域，图染色问题起源于著名的四色猜想，随着信息技术的不断发展，从最开始的四色猜想问题发展到现在，在模式识别，生物信息，网络模型理论等领域具有广泛的应用背景。

连通性不仅是图论中最基本的一个概念之一，还是衡量网络可靠性等的重要指标。将图的染色与连通性结合产生出了一种新的染色，这个新的概念是由Chartrand等人于2008年在文献[1]中引进的，接着Ericksen在文献[2]中首先提出了彩虹连通染色数。进一步，Chakraborty等人[3]证明了对一个给定的边染色图，判定该染色是否是G的一个彩虹连通染色是NP-完全的。即使把图限制在二部图[4]和正则图[5]上，上述问题仍然是NP-完全的。有关彩虹连通更多的结果，请读者参考[6]-[11]及其文中的参考文献。

众所周知，有两种途径可以研究图的连通性，一种是使用路，另一种是使用割。使用路来研究图的染色连通性已经有很多好的结果，因此，考虑用图的割来研究图的染色连通性是很自然的。在2018年，Chartrand等人[12]首次从彩虹边割的角度，通过引入图的彩虹不连通的概念来研究图的染色连通性，图的彩虹不连通数在商品流通，信号传递等实际应用中有着重要的作用。

本文所考虑的图都是连通的、简单的、有限图。对没有说明的术语和概念可参考[13]，设$G=\left(V,E\right)$ 是顶点集为V，边集为E的有限简单图，用$v\left(G\right)$ 和$e\left(G\right)$ 分别记图G中的顶点数和边数。顶点V在G中的度数是与V关联的边数，用$d_G\left(v\right)$ 表示，用$\delta \left(G\right)$ 表示图的最小度，用$\Delta \left(G\right)$ 表示图的最大度。路$P\left(V,E\right)$ 是一个非空图，其顶点集和边集分别为$V=\left\{x_0,x_1,\cdots ,x_k\right\}$ ， $E=\left\{x_0{x}_1,x_1{x}_2,\cdots ,x_{k-1}{x}_k\right\}$ ，这里所有的$x_i$ 均互不相同，顶点$x_0$ 和$x_k$ 由路P连接，并称它们为路的端点或顶端，一条路上的边数称为路的长度。如果非空图中G的任意两个顶点之间均有一条路相连，就称G是连通的。

一个连通图G的点割是一个点集F使得$G-F$ 是不连通的，一个$x-y-$ 点割是一个点集F使得在$G-F$ 中x和y是在不同的连通分支，其中顶点x和y是不相邻的。类似的，一个连通图G的边割是一个边集F使得$G-F$ 是不连通的。我们用$\lambda \left(G\right)$ 表示图G的最小边割的边数。显然，$\lambda \left(G\right)\le \delta \left(G\right)$ 。

用$\left[k\right]$ 表示整数的集合$\left\{1,2,\cdots ,k\right\}$ ，假设G是一个图，它的一个边染色C是指：$E\left(G\right)\to \left[k\right]$ ，$k\in N$ 其中相邻边的颜色可以相同。若e是图G的一条边，我们用$c\left(e\right)$ 表示边e的颜色。当图G的相邻边在染色c中的颜色不同，边染色c被称为正常的。图G的正常边染色中所需要的最少的颜色数被称为图G的边色数，用$x^{\prime }\left(G\right)$ 表示。根据Vizing [6]的一个著名定理，对每个非空图G，我们有$\Delta \left(G\right)\le x^{\prime }\left(G\right)\le \Delta \left(G\right)+1$ 。若$x^{\prime }\left(G\right)=\Delta \left(G\right)$ ，则图G是第一类图；若$x^{\prime }\left(G\right)=\Delta \left(G\right)+1$ ，则图G是第二类图。如果一条路的所有边的颜色都不相同，那么称这条路是彩虹的。在边染色图G中，如果一个顶点所关联的边的颜色两两不同，那么称这个顶点是正常的。

一个彩虹边割是边染色图G的一个边割R，并且边集R中的所有边都有不同的颜色。令u和v是图G中的两个顶点，如果G的一个彩虹边割R满足u和v属于$G\backslash R$ 的不同连通分支，则称边集R是G的一个彩虹$u-v-$ 边割。设G是一个非平凡的边染色连通图，如果图G的一个边割R中没有任何两条边是相同的颜色，则称R是图G的一个彩虹边割。u和v是图G的任意两个不相同的顶点，如果图G的一个彩虹边割R满足u和v属于$G-R$ 的不同连通分支，则称图G的这个边染色为彩虹不连通染色。对于一个连通图G，图G的一个彩虹不连通染色数是使得图G彩虹不连通所要求的最少的颜色数，用$rd\left(G\right)$ 表示。

2. 主要结果

2.1. 彩虹不连通染色数

Chartrand等人于2018年第一次定义了彩虹不连通染色的概念，并且给出了一个很好的结果。

命题1 [12]若G是一个非平凡的连通图，则

$\lambda \left(G\right)\le {\lambda }^{+}\left(G\right)\le rd\left(G\right)\le {\chi }^{\prime }\left(G\right)\le \Delta \left(G\right)+1$

由图的不连通染色的定义知，下面的结果是显然的。

命题2 [12]设正整数$n\ge 2$ ，则$rd\left(k_n\right)=n-1$ 。

图的顶点数固定，减少图的边数，不会使其彩虹不连通数增加，所以顶点数为n的图彩虹不连通数小于等于完全图的彩虹不连通数，于是有以下结果。

命题3 [12]若H是连通图G的一个连通子图，则$rd\left(H\right)\le rd\left(G\right)$ 。

作者完全刻画了彩虹不连通染色数等于1，2和$n-1$ 的图。

命题4 [12]设G是一个非平凡的连通图，则$rd\left(G\right)=1$ 当且仅当G是树。

定理5 [12]设G是一个非平凡的连通图，则$rd\left(G\right)=2$ 当且仅当G的每个块要么是$k_2$ 要么是一个圈，并且G至少有一个块是圈。

定理6 [12]设G是一个非平凡的连通图，则$rd\left(G\right)=n-1$ 当且仅当G包含至少两个度为$n-1$ 的顶点。

给定正整数k和n，其中$1\le k\le n-1$ ，作者在[12]中确定了顶点数为n且满足$rd\left(G\right)=k$ 的连通图G的边数的最小值。

定理7 [12]假设k和n是正整数，其中$1\le k\le n-1$ ，则顶点数为n且满足$rd\left(G\right)=k$ 的连通图G的最小边数是$n+k-2$ 。

对于给定图的彩虹不连通数求边的最大值问题，Bai等人得到了很好的结果。

定理8 [14]假设k和n是正整数，其中$1\le k\le n-1$ ，则顶点数为n且满足$rd\left(G\right)=k$ 的连通图G的最大边数是$\lfloor \frac{\left(k+1\right)\left(n-1\right)}{2}\rfloor$ 。

接着Bai等人解决了图的彩虹不连通数的两类Erdös-Gallai型问题。

问题1给定两个正整数n和k，其中$1\le k\le n-1$ ，计算满足以下性质的函数$g\left(n,k\right)$ 的最大整数值：对于顶点数为n的任意图G，如果$\left|E\left(G\right)\right|\le g\left(n,k\right)$ ，那么$rd\left(G\right)\le k$ 。

问题2给定两个正整数n和k，其中$1\le k\le n-1$ ，计算满足以下性质的函数$f\left(n,k\right)$ 的最小整数值：对于顶点数为n的任意图G，如果$\left|E\left(G\right)\right|\ge f\left(n,k\right)$ ，那么$rd\left(G\right)\ge k$ 。

Bai等人利用上述给定彩虹不连通数求解图的边数的最大值和最小值的结论，他们得到了$g\left(n,k\right)$ 和$f\left(n,k\right)$ 的确切值。

定理9 [14]对于正整数n和k且满足$1\le k\le n-1$ ，则

$g\left(n,k\right)=\{\begin{array}{ll}\frac{n\left(n-1\right)}{2},\hfill & 如果k=n-1,\hfill \\ n+k-2,\hfill & 如果1\le k\le n-2.\hfill \end{array}$

定理10 [14]对于正整数n和k且满足$1\le k\le n-1$ ，则

$f\left(n,k\right)=\{\begin{array}{ll}n-1,\hfill & 如果k=1,\hfill \\ \lfloor \frac{k\left(n-1\right)}{2}\rfloor +1,\hfill & 如果2\le k\le n-1.\hfill \end{array}$

Nordhaus-Gaddum-型的结果是研究图及其补图的某个参数的和或积的(紧的)下界或上界的，下面是图的彩虹不连通数的Nordhaus-Gaddum-型的结果。

定理11 [14]若$G$ 和$\overline{G}$ 是连通图，则$n-2\le rd\left(G\right)+rd\left(\overline{G}\right)\le 2n-5$ ，且 $n-3\le rd\left(G\right)\cdot rd\left(\overline{G}\right)\le \left(n-2\right)\left(n-3\right)$ ，此外，这些界都是紧的。

2.2. 彩虹不连通数的界

下面是一些特殊图类的彩虹不连通数，包括完全多部图，正则图，关于边色数的临界图等等。

定理12 [14]若$G=K_{n_1,n_2,\cdots ,n_k}$ 是一个阶数为n的完全k-部图，其中$k\ge 2$ 并且$n_1\le n_2\le \cdots \le n_k$ ，则

$rd\left(K_{n_1,n_2,\cdots ,n_k}\right)=\{\begin{array}{ll}n-n_2,\hfill & 如果n_1=1,\hfill \\ n-n_1,\hfill & 如果n_1\ge 2.\hfill \end{array}$

定理13 [14]若G是关于边色数极小的连通图，则$rd\left(G\right)\le \Delta \left(G\right)$ 。

定理14 [14]若G是一个连通的k-正则图，则$k\le rd\left(G\right)\le K+1$ 。

定理15 [14]若G是一个连通的阶数为n的$\left(n-k\right)$ -正则图，其中$1\le k\le 4$ ，则$rd\left(G\right)=n-k$ 。

定理16 [14]令k是一个奇整数，并且G是一个k-边连通k-正则图，则${\chi }^{\prime }\left(G\right)=k$ 当且仅当$rd\left(G\right)=k$ 。

Bai等人通过研究线图的顶点彩虹不连通染色数，确定了两个图的彩虹不连通染色数的上界。

定理17 [15]设G是一个图且$L\left(G\right)$ 是G的线图，则$rd\left(G\right)\le rvd\left(L\left(G\right)\right)$ 。

定理18 [15]设G是一个$\delta \left(G\right)\ge 4$ 的图且$L\left(G\right)$ 是G的线图，如果则$rd\left(G\right)=rvd\left(L\left(G\right)\right)$ ，则$rd\left(G\right)={\chi }^{\prime }\left(G\right)$ 。

本文对图的彩虹不连通染色数进行了全面的讨论，通过这些研究成果，我们为图的彩虹不连通染色数的研究提供了一定的理论支撑和实际应用参考，也为相关领域的进一步研究提供了重要的基础和借鉴。此外，这些研究还可以与其他相关领域进行有益的结合。例如，可以将图的彩虹不连通染色数与图的同构性、网络中的路由问题等进行结合，从而进一步研究彩虹不连通染色数的拓展问题，如在多种约束条件下的彩虹不连通染色数的计算和优化，以及图的其他染色问题的研究。

基金项目

喀什大学校级一般项目(20222766)。