浙江师范大学数学系，浙江 金华

收稿日期：2021年6月12日；录用日期：2021年7月1日；发布日期：2021年7月15日

摘要

对于边染色图G，若G的每一条边都被染不同的颜色，则称G为彩虹图。对于给定的图G和H，使得G中不存在任何彩虹子图H的最大边染色数，叫做H在G中的anti-Ramsey数，记作AR(G,H)。本文确定了完全多部图中C₄的anti-Ramsey数的精确值，研究结论覆盖了完全图和完全分裂图中的相关结果。

关键词

Anti-Ramsey数，彩虹C₄，完全多部图

Anti-Ramsey Number of 4-Cycle in Complete Multipartite Graphs

Ting Yu, Kangyun Zhong

Department of Mathematics, Zhejiang Normal University, Jinhua Zhejiang

Received: Jun. 12^th, 2021; accepted: Jul. 1^st, 2021; published: Jul. 15^th, 2021

ABSTRACT

A given edge-colored graph G is called rainbow if all its edges have distinct colors. Given two graphs G and H, the maximum colors in an edge-coloring of G without any rainbow H is called the anti-Ramsey number of H in G, which is denoted by AR(G,H). In this paper, we determine the anti-Ramsey number of 4-cycle in complete multipartite graphs. The results cover the results in complete and complete split graphs obtained previously.

Keywords:Anti-Ramsey Number, Rainbow C₄, Complete Multipartite Graph

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文中涉及的图都是有限无向的简单图。对于边染色图G，若G的每一条边都被染不同的颜色，则称G为彩虹图。对于给定的图G和H，使得G中不存在任何彩虹子图H的最大边染色数，叫做H在G中的anti-Ramsey数，记作AR(G,H)。Anti-Ramsey数是由Erdös等人于上世纪70年代首次提出，并且揭示了图的anti-Ramsey数与Turán数之间密切相关。此外，他们还提出了任意圈在完全图中的anti-Ramsey数的猜想，结论如下：

猜想1.1. [1] 对任意正整数 $k\ge 3$，都有 $AR\left(K_n,C_k\right)=n\left(\frac{k-2}{2}+\frac{1}{k-1}\right)+O\left(1\right)$。

早期关于anti-Ramsey数的结论主要以完全图为母图，考虑单个图在完全图中的anti-Ramsey数，比如说：路，圈，团，匹配等，可以参考 [2] [3] [4]，本文主要介绍关于 $C_{\text{4}}$ 的结论。首先，Alon [5]、Jiang & West [6] 解决了完全图中 $C_{\text{4}}$ 的anti-Ramsey数，得到如下结论：

定理1.2. [5] [6] 对任意 $n\ge 4$，都有 $AR\left(K_n,C_4\right)=\lfloor \frac{4n}{3}\rfloor -1$。

Axenovich等人 [7] 率先将anti-Ramsey数问题推广到完全二部图，他们证明了完全二部图中任意偶圈的anti-Ramsey数，涉及 $C_{\text{4}}$ 的结论如下：

定理1.3. [7] 对任意正整数 $n_1,n_2$ 都有 $AR\left(K_{n_1,n_2},C_4\right)=n_1+n_2-1$。

完全分裂图作为完全多部图的一种特殊情形，短圈 $C_{\text{4}}$ 在完全分裂图中的anti-Ramsey数由Lv等人 [8] 证明，结论如下：

定理1.4. [8] 对任意 $n+s\ge 4$，以及 $n\ge 2$，都有

$AR\left(K_n+\overline{K_s},C_4\right)=\{\begin{array}{l}n+s+\lfloor \frac{n+s}{3}\rfloor -1,如果n\ge 2s;\hfill \\ n+s+\lfloor \frac{n}{2}\rfloor -1,如果2\le n\le 2s.\hfill \end{array}$

为了下文叙述方便，我们先定义本文中常用的一些图论的术语和符号，并给出一些通用的特殊定义及符号。在图G中， $V\left(G\right)$ 和 $E\left(G\right)$ 分别为G的顶点集和边集。此外， $\left|V\left(G\right)\right|$，$\left|E\left(G\right)\right|$ 以及 $\omega \left(G\right)$ 分别称为顶点数，边数和连通分支数。对于任意点 $v\in V\left(G\right)$，与 $v$ 相关联的边的数目叫做 $v$ 在G的度，记作 $d_G\left(v\right)$。图G中，点不交的 $C_{\text{3}}$ 的最大数量记做 $\text{Γ}\left(G\right)$。

若G是一个顶点序列为 $\left\{v_1,v_2,\cdots ,v_n\right\}$ 的图，且满足两个顶点是邻接的当且仅当它们在顶点的序列是前后相继的，则称G为路，记作 $P_n=\left(v_1,v_2,\cdots ,v_n\right)$，其中 $v_1$ 和 $v_n$ 分别叫做路 $P_n$ 的起点和终点。而若G可由一条路连接起点和终点得到，则称G为圈，记作 $C_n=\left[v_1,v_2,\cdots ,v_n\right]$。此外，令 ${\alpha }^{\prime }\left(G\right)$ 表示G中最大匹配的边数。对于图G和H，若满足 $V\left(H\right)\subseteq V\left(G\right)$ 和 $E\left(H\right)\subseteq E\left(G\right)$，则称H是G的一个子图，记作 $H\subseteq G$。如果 $V\left(H\right)=V\left(G\right)$，则H叫做G的生成子图。

对于边染色图G，任意 $e\in E\left(G\right)$，令 $c\left(e\right)$ 表示 $e$ 的颜色。若子图 $H\subseteq G$，则 $c\left(H\right)$ 表示子图H所有边的颜色集合。任意 $v\in V\left(G\right)$，从G中删除点 $v$ 而损失的颜色数叫做点 $v$ 的饱和度，记作 $l\left(v\right)$，即 $l\left(v\right)=\left|c\left(G\right)\right|-\left|c\left(G-v\right)\right|$。若与 $v$ 相关联的边 $e$，满足 $c\left(e\right)\in c\left(G\right)\backslash c\left(G-v\right)$，则称 $e$ 为 $v$ 的饱和边。

2. 引理

引理2.1. 设 $K_{n_1,n_2,\cdots ,n_m}$ 的部集分别为 $X_1,X_2,\cdots ,X_m$，其中 $\left|X_i\right|=n_i,i=1,2,\cdots ,m$ 且 $n_1\ge n_2\ge \cdots \ge n_m\ge 1$。对任意 $m\ge 2$，都有

${\alpha }^{\prime }\left(K_{n_1,n_2,\cdots ,n_m}\right)=\{\begin{array}{l}\lfloor \frac{n_1+n_2+\cdots +n_m}{2}\rfloor ,如果n_1<n_2+\cdots +n_m;\hfill \\ n_2+\cdots +n_m,如果n_1\ge n_2+\cdots +n_m.\hfill \end{array}$

证明：设 $M$ 为 $K_{n_1,n_2,\cdots ,n_m}$ 的一个最大匹配，使得 $M$ 中尽可能多的包含一个端点属于 $X_i$ 的边。此外， 令 $V_1=V\left(K_{n_1,n_2,\cdots ,n_m}\right)\backslash V\left(M\right)$。显然， $V_1$ 中的所有点都属于同一个部集，否则与 $M$ 的定义相矛盾。

断言1. 若 $V_1\cap X_1\ne \varnothing$，则对任意边 $e\in M$，它都包含一个属于 $X_1$ 的端点。

证明：假设存在一个点 $w$ 和 $M$ 中的一条边 $uv$，使得 $w=V_1\cap X_1$，且 $u,v\notin X_1$。令 $u\in X_i,v\in X_j,i\ne 1\ne j$。因为 $i\ne 1$，我们有 $uw\in E\left(K_{n_1,n_2,\cdots ,n_m}\right)$。现在我们可以通过增加 $uw$，删除 $uv$ 得到一个新的 $M$，这与 $M$ 的定义相矛盾，断言1证明完毕。

断言2. 若 $\left|V_1\right|\ge 2$，则 $V_1\subseteq X_i$。

证明：注意 $V_1$ 中的所有点都属于同一个部集。假设 $\left|V_1\right|\ge 2$ 且 $V_1\subseteq X_i,i\ne 1$。令 $u,v\in V_1$。因为 $n_1\ge n_i$，所以必定存在一条边 $xy\in M$，使得 $x\in X_i,y\in X_j,i\ne j$。又因为 $i\ne 1\ne j$，我们有 $ux,vy\in E\left(K_{n_1,n_2,\cdots ,n_m}\right)$。

现在我们可以由 $M$ 通过增加两条边 $ux,vy$，删除一条边 $xy$ 得到一个更大的匹配，这与 $M$ 的定义相矛盾。断言2证明完毕。

为了完成证明，下面我们分两种情形进行讨论。

情形1. $V_1\cap X_1\ne \varnothing$。

由断言1可知， $M$ 中的所有边都有一个属于 $X_1$ 的端点。因此， $n_1\ge n_2+n_3+\cdots +n_m+1$，并且此时 ${\alpha }^{\prime }\left(K_{n_1,n_2,\cdots ,n_m}\right)=n_2+\cdots +n_m$。

情形2. $V_1\cap X_1=\varnothing$。

由断言2可知， $\left|V_1\right|\le 1$。因此， $n_1\le n_2+\cdots +n_m$，并且此时 ${\alpha }^{\prime }\left(K_{n_1,n_2,\cdots ,n_m}\right)=\lfloor \frac{n_1+\cdots +n_m}{2}\rfloor$。显然，当 $n_1=n_2+\cdots +n_m$ 时， ${\alpha }^{\prime }\left(K_{n_1,n_2,\cdots ,n_m}\right)=\lfloor \frac{n_1+\cdots +n_m}{2}\rfloor =n_2+\cdots +n_m$

引理2.1证明完毕。

由引理2.1，我们得到如下推论。

推论2.2. 设 $n={\displaystyle {\sum }_{i=1}^n{n}_i}$，完全多部图 $K_{n_1,n_2,\cdots ,n_m}$ 存在完美匹配当且仅当 $n_1=n_2+\cdots +n_m$，或者 $n_1<n_2+\cdots +n_m$ 且 $n$ 为偶数。

引理2.3.对任意 $m\ge 3$，都有

$\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)=\{\begin{array}{l}{n}_3+\cdots +n_m,如果n_2\ge n_3+\cdots +n_m;\hfill \\ \lfloor \frac{n_2+\cdots +n_m}{2}\rfloor ,如果n_2<n_3+\cdots +n_m且n_1>\lfloor \frac{n_2+\cdots +n_m}{2}\rfloor ;\hfill \\ \lfloor \frac{n_1+\cdots +n_m}{3}\rfloor ,如果n_2<n_3+\cdots +n_m且n_1\le \lfloor \frac{n_2+\cdots +n_m}{2}\rfloor .\hfill \end{array}$

证明：设 $\Gamma$ 为 $K_{n_1,n_2,\cdots ,n_m}$ 中包含最大数目点不交的 $C_{\text{3}}$ 的集合，使得 $\Gamma$ 中尽可能多的包含一个顶点属于 $X_1$ 的 $C_{\text{3}}$。换言之，在保证数目最大的前提下我们优先挑选那些有一个顶点属于 $X_1$ 的 $C_{\text{3}}$。令 $V_1=V\left(K_{n_1,n_2,\cdots ,n_m}\right)\backslash V\left(\Gamma \right)$。显然， $V_1$ 中的有点至多属于两个部集，否则与 $\Gamma$ 的定义相矛盾。令 $n=n_1+n_2+\cdots +n_m$，$n^{*}=n_2+\cdots +n_m$。

断言3. 若 $V_1\cap X_1\ne \varnothing$，则对任意 $C_3\in \Gamma$，它都包含一个属于 $X_i$ 的顶点。

证明：假设存在一个点 $s$，以及 $\Gamma$ 中的一个 $C_3=\left[u,v,w\right]$，使得 $s\in V_1\cap X_1$ 且 $u,v,w\notin X_1$。令 $u\in X_i,v\in X_j,w\in X_z,i\ne j\ne z\ne 1$。现在我们可以由 $\Gamma$ 通过增加 $\left[u,v,s\right]$，删除 $\left[u,v,w\right]$ 来得到一个新的 $\Gamma$，这与 $\Gamma$ 的定义相矛盾。

断言3证明完毕。

断言4. 若 $\left|V_1\right|\ge 3$，则 $V_1\cap X_1\ne \varnothing$。

证明：注意 $V_1$ 中的所有点属于至多两个部集。假设 $\left|V_1\right|\ge 3$ 且 $V_1\cap X_1\ne \varnothing$。如果 $V_1$ 中的所有点属于同一个部集，不失一般性，我们假设 $V_1\subseteq X_i,s_1,s_2,s_3\in X_i\cap V_1$，其中 $i\ne 1$。因为 $n_1\ge n_i$，所以 $\Gamma$ 中必定存在两个点不交的 $C_3$，不妨设为 $\left[u_1,v_1,w_1\right]$ 和 $\left[u_2,v_2,w_2\right]$，使得 $u_1,u_2\in X_1,v_1,v_2,w_1,w_2\notin X_i$。现在我们可以由 $\Gamma$ 通过增加 $\left[s_1,v_1,w_1\right]$，$\left[s_2,u_2,w_2\right]$，以及 $\left[s_3,u_1,v_2\right]$，删除 $\left[u_1,v_1,w_1\right]$ 和 $\left[u_2,v_2,w_2\right]$ 得到一个更大的点不交的 $C_3$ 的集合，这与 $\Gamma$ 的定义相矛盾。

因此， $V_1$ 中的所有点恰恰属于两个部集，不失一般性，假设 $\left|X_i\cap V_1\right|\ge 2,\left|X_j\cap V_1\right|\ge 1$ 以及 $s_1,s_2\in X_i\cap V_1,s_3\in X_j\cap V_1,i\ne 1\ne j$。因为 $n_1\ge n_i$，所以 $\Gamma$ 中必定存在一个 $C_3$，不妨设为 $\left[u_1,v_1,w_1\right]$，使得 $u_1\in X_1,v_1,w_1\notin X_i$。现在我们可以由 $\Gamma$ 通过增加 $\left[u_1,v_1,w_1\right]$ 和 $\left[s_2,s_3,u_1\right]$，删除 $\left[u_1,v_1,w_1\right]$ 得到一个更大的点不交的 $C_3$ 的集合，这与 $\Gamma$ 的定义相矛盾。断言4证明完毕。

为了完成证明，下面我们分三种情形进行讨论。

情形1. $V_1\subseteq X_1$。

由断言3可知，对任意 $C_3\in \Gamma$，它都包含一个属于 $X_1$ 的端点。因此， $n_1>\lfloor \frac{n_2+\cdots +n_m}{2}\rfloor$。另一方面， $K_{n_2,n_3,\cdots ,n_m}$ 中必定存在一个完美匹配。由推论2.2，我们有 $n_2=n_3+\cdots +n_m$ 或者 $n_2<n_3+\cdots +n_m$ 且 $n^{*}$ 为偶数。显然，此时 $\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)={\alpha }^{\prime }\left(K_{n_2,n_3,\cdots ,n_m}\right)=\frac{n_2+\cdots +n_m}{2}$。

情形2. $V_1\not\subset X_1$ 且 $V_1\cap X_1\ne \varnothing$。

由断言3可知，对任意 $C_3\in \Gamma$，它都包含一个属于 $X_1$ 的端点。另一方面，因为 $V_1\not\subset X_1$，所以 $K_{n_2,n_3,\cdots ,n_m}$ 中不存在完美匹配。由推论2.2，我们有 $n_2\ge n_3+\cdots +n_m+1$ 或者 $n_2<n_3+\cdots +n_m$ 且 $n^{*}$ 为奇数。当 $n_2\ge n_3+\cdots +n_m+1$ 时， $\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)={\alpha }^{\prime }\left(K_{n_2,n_3,\cdots ,n_m}\right)=n_3+\cdots +n_m$。此外，当 $n_2<n_3+\cdots +n_m$ 且 $n^{*}$ 为奇数时， ${\alpha }^{\prime }\left(K_{n_2,n_3,\cdots ,n_m}\right)=\lfloor \frac{n_2+\cdots +n_m}{2}\rfloor$ 所以 $n_1>\lfloor \frac{n_2+\cdots +n_m}{2}\rfloor$。显然，此时 $\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)={\alpha }^{\prime }\left(K_{n_2,n_3,\cdots ,n_m}\right)=\lfloor \frac{n_2+\cdots +n_m}{2}\rfloor$。

情形3. $V_1\cap X_1=\varnothing$。

由断言4可知， $\left|V_1\right|\le 2$。因为 $V_1\cap X_1=\varnothing$，所以 $n_1\le \lfloor \frac{n_2+n_3+\cdots +n_m}{2}\rfloor$ 且 $n_2\le n_3+\cdots +n_m$。显然，此时 $\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)=\lfloor \frac{n_1+\cdots +n_m}{3}\rfloor$。引理2.3证明完毕。

3. 主要结果

基于以上引理，下面开始证明我们的主要结论。

构造3.1. 设 $K_{n_1,n_2,\cdots ,n_m}\left(m\ge 3\right)$ 的部集分别为 $X_1,X_2,\cdots ,X_m$，其中 $\left|X_i\right|=n_i,i=1,2,\cdots ,m$，且 $n_1\ge n_2\ge \cdots \ge n_m$。此外，令 $\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)=t$，此时我们给出 $K_{n_1,n_2,\cdots ,n_m}$ 的一种边染色 $c$，具体染色方法如下：

首先，在 $K_{n_1,n_2,\cdots ,n_m}$ 中尽可能多的取出点不交的 $C_3$，不妨分别设为 $T_1,T_2,\cdots ,T_t$，令 $\left\{T_{t+1},T_{t+2},T_{n-2t}\right\}$ 表示由剩下的点构成的集合。然后，将 $T_1,T_2,\cdots ,T_t$ 中的所有边都染不同的颜色。最后，对任意 $1\le i,j\le n-2t$，若 $i<j$，则将 $T_i$ 和 $T_j$ 之间的所有边都染新颜色 $i$。

不难发现，由构造3.1给出的 $K_{n_1,n_2,\cdots ,n_m}$ 的边染色 $c$ 中不包含任何彩虹子图 $C_4$，并且 $c$ 中恰恰使用了 ${\displaystyle {\sum }_{i=1}^m{n}_i}+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-1$ 种颜色。因此，构造3.1表明 $K_{n_1,n_2,\cdots ,n_m}$ 中 $C_4$ 的anti-Ramsey数不小于 ${\displaystyle {\sum }_{i=1}^m{n}_i}+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-1$，即

$AR\left(K_{n_1,n_2,\cdots ,n_m},C_4\right)\ge {\displaystyle {\sum }_{i=1}^m{n}_i}+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-1.$

定理 3.2. 对任意 $m\ge 3$，都有 $AR\left(K_{n_1,n_2,\cdots ,n_m},C_4\right)={\displaystyle {\sum }_{i=1}^m{n}_i}+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-1$。

证明：由构造3.1我们已经证明 $AR\left(K_{n_1,n_2,\cdots ,n_m},C_4\right)\ge {\displaystyle {\sum }_{i=1}^m{n}_i}+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-1$，因此这里我们只需继续证明 $K_{n_1,n_2,\cdots ,n_m}$ 中 $C_4$ 的anti-Ramsey数不大于 ${\displaystyle {\sum }_{i=1}^m{n}_i}+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-1$，即

$AR\left(K_{n_1,n_2,\cdots ,n_m},C_4\right)\le {\displaystyle {\sum }_{i=1}^m{n}_i}+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-1.$

设 $n=n_1+n_2+\cdots +n_m$，对 $K_{n_1,n_2,\cdots ,n_m}$ 的顶点数 $n$ 用归纳法。由引理1.2可知，上界对 $n=m$ 成立。令 $n\ge m+1$，并假设上界对顶点数小于 $n$ 也成立。

假设存在一个恰恰使用了 $n+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)$ 种颜色的 $K_{n_1,n_2,\cdots ,n_m}$ 的边染色，使得 $K_{n_1,n_2,\cdots ,n_m}$ 中不包含任何彩虹子图 $C_4$。显然，对任意点 $v\in V\left(K_{n_1,n_2,\cdots ,n_m}\right)$，都有 $\Gamma \left(K_{n_1,n_2,\cdots ,n_m}-v\right)\le \Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)$。注意 $K_{n_1,n_2,\cdots ,n_m}$ 不包含任何彩虹子图 $C_4$。因此， $K_{n_1,n_2,\cdots ,n_m}-v$ 中也不包含任何彩虹子图 $C_4$。根据归纳假设可知， $\left|c\left(K_{n_1,n_2,\cdots ,n_m}-v\right)\right|\le AR\left(K_{n_1,n_2,\cdots ,n_m}-v,C_4\right)\le n+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-2$。

因此，对任意点 $v\in V\left(K_{n_1,n_2,\cdots ,n_m}\right)$，都有

$\begin{array}{c}l\left(v\right)=\left|c\left(K_{n_1,n_2,\cdots ,n_m}\right)\right|-\left|c\left(K_{n_1,n_2,\cdots ,n_m}-v\right)\right|\\ \ge n+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-\left(n+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-2\right)\\ =2\end{array}$ (1)

为了完成证明，需要引入下面这些断言。

断言5. 对任意点 $v\in V\left(K_{n_1,n_2,\cdots ,n_m}\right)$，若 $vx,vy$ 是 $v$ 的两条不同颜色的饱和边，则 $x$ 和 $y$ 必定属于不同的部集。

证明：假设存在一个点 $v\in V\left(K_{n_1,n_2,\cdots ,n_m}\right)$，$vx$ 和 $vy$ 是 $v$ 的两条颜色不同的饱和边，使得 $x,y$ 属于同一个部集。不失一般性，我们假设 $v\in X_p,x,y\in X_q,1\le p\ne q\le m$。由不等式(1)可知，至少存在 $x$ 的一条饱和边，不妨设为 $xz$，使得 $c\left(xz\right)\ne c\left(vx\right)$。令 $z\in X_r,1\le r\ne q\le m$。因为 $vy$ 是 $v$ 的一条饱和边，所以 $c\left(xz\right)\ne c\left(vy\right)$。

如果 $r\ne p$ 则 $v,x,y,z$ 为属于三个不同部集的四个点，其中 $x,y\in X_p$。现在我们考虑边 $yz$ 的颜色。不难发现，因为 $xz$ 是 $x$ 的一条饱和边，可知 $c\left(yz\right)\ne c\left(xz\right)$。此外，因为 $vx$ 和 $vy$ 是 $v$ 的两条不同颜色的饱和边，我们有 $c\left(vx\right)\ne c\left(yz\right)\ne c\left(vy\right)$。因此，此时存在一个彩虹子图 $C_4=\left[v,x,z,w\right]$，矛盾。所以 $r=p$，此时 $v,x,y,z$ 为属于两个不同部集的四个点，其中 $x,y\in X_q,v,z\in X_p$。同理可得， $c\left(yz\right)\notin \left\{c\left(vx\right),c\left(vy\right),c\left(xz\right)\right\}$。因此，此时同样存在一个彩虹子图 $C_4=\left[v,x,z,y\right]$，矛盾。断言5证明完毕。

断言6. 对任意点 $v\in V\left(K_{n_1,n_2,\cdots ,n_m}\right)$，都有 $l\left(v\right)=2$。

证明：由不等式(1)可知，对任意点 $v\in V\left(K_{n_1,n_2,\cdots ,n_m}\right)$，都有 $l\left(v\right)\ge 2$。因此，我们只需证明上界 $l\left(v\right)\le 2$。假设存在一个点 $v\in V\left(K_{n_1,n_2,\cdots ,n_m}\right)$，使得 $l\left(v\right)\ge 3$。不失一般性，设 $v\in X_p,1\le p\le m$。由断言5可知，存在至少 $v$ 的三条颜色不同的饱和边，不妨设为 $vx,vy,vz$，使得 $x\in X_q,y\in X_r$，以及 $z\in X_s,1\le p\ne q\ne r\ne s\le m$。根据不等式(1)可知，至少存在 $x$ 的一条饱和边，不妨设为 $xw$，使得 $c\left(xw\right)\ne c\left(vx\right)$。令 $w\in X_h$。因为 $vx,vy,vz$ 是 $v$ 的三条颜色不同的饱和边，我们有 $c\left(xw\right)\notin \left\{c\left(vx\right),c\left(vy\right),c\left(vz\right)\right\}$。如果 $h\notin \left\{p,r,s\right\}$，则 $v,x,y,w$ 为属于不同部集的四个点。现在我们考虑 $yw$ 的颜色。因为 $xw$ 是 $x$ 的一条饱和边，可知 $c\left(yw\right)\ne c\left(xw\right)$。此外，因为 $vx,vy$ 是 $v$ 的两条颜色不同的饱和边，我们有 $c\left(vx\right)\ne c\left(yw\right)\ne c\left(vy\right)$。因此，此时存在一个彩虹子图 $C_4=\left[v,x,w,y\right]$，矛盾。

因此， $h\in \left\{p,r,s\right\}$，由 $X_r$ 和 $X_r$ 的对称性，我们只考虑 $h=p$ 或者 $h=r$ 这两种情形。如果 $h=p$，则 $v,x,y,w$ 为属于三个不同部集的四个点，其中 $v,w\in X_p$。同理可得， $c\left(yw\right)\notin \left\{c\left(vx\right),c\left(vy\right),c\left(xw\right)\right\}$。因此，此时存在一个彩虹子图 $C_4=\left[v,x,w,y\right]$，矛盾。所以 $h=r$，则 $v,x,y,w$ 为属于不同部集的四个点。同理可得 $c\left(zw\right)\notin \left\{c\left(vx\right),c\left(vz\right),c\left(xw\right)\right\}$。因此，此时同样存在一个彩虹子图 $C_4=\left[v,x,w,y\right]$，矛盾。断言6证明完毕。

断言7. 对任意两个点 $u,v\in V\left(K_{n_1,n_2,\cdots ,n_m}\right)$，若 $uv$ 是 $u$ 的饱和边，则 $uv$ 也是 $v$ 的饱和边。

证明：假设存在两个点 $u,v\in V\left(K_{n_1,n_2,\cdots ,n_m}\right)$，使得 $uv$ 是 $u$ 的饱和边，但 $uv$ 不是 $v$ 的饱和边。令 $u\in X_p,v\in X_q$。由断言5和断言6可知，存在 $u$ 的一条饱和边，不妨设为 $ux$，使得 $c\left(ux\right)\ne c\left(uv\right)$，其中 $x\in X_r,1\le r\ne q\le m$。根据断言6，我们有 $l\left(v\right)=2$，所以存在 $v$ 的两条颜色不同的饱和边，不妨设为 $vy,vz$。因为 $ux$ 是 $u$ 的饱和边，可知 $c\left(vy\right)\ne c\left(ux\right)\ne c\left(vz\right)$。同时，根据假设可知， $c\left(vy\right)\ne c\left(uv\right)\ne c\left(vz\right)$。如果 $y\notin X_r$，则我们考虑边 $xy$ 的颜色。因为 $vy$ 是 $v$ 的饱和边，可知 $c\left(xy\right)\ne c\left(vy\right)$。此外，因为 $uv$ 和 $ux$ 是 $v$ 的两条颜色不同的饱和边，我们有 $c\left(uv\right)\ne c\left(xy\right)\ne c\left(ux\right)$。因此，此时存在一个彩虹子图 $C_4=\left[u,v,y,x\right]$，矛盾。所以 $y\in X_r$。同理可得， $z\in X_r$，这与断言5相矛盾。断言7证明完毕。

断言8. 若 $xy$ 既为 $x$ 的饱和边，又为 $y$ 的饱和边，则颜色 $c\left(xy\right)$ 只用于染边 $xy$。

证明：由饱和边的定义，因为 $xy$ 为 $x$ 的饱和边，所以颜色 $c\left(xy\right)$ 只用于染与 相关联的边。同理，因为 $xy$ 为 $y$ 的饱和边，所以颜色 $c\left(xy\right)$ 只用于染与 $y$ 相关联的边。因此，颜色 $c\left(xy\right)$ 只用于染边 $xy$。断言8证明完毕。

令G为 $K_{n_1,n_2,\cdots ,n_m}$ 的一个生成子图，使得若 $uv\in E\left(G\right)$，则 $uv$ 是 $u$ 的饱和边，或者 $uv$ 是 $v$ 的饱和边。此外，设 $G_i$ 为G任意一个连通分支，其中 $i\in \left\{1,2,\cdots ,\omega \left(G\right)\right\}$。由断言7和断言8可知，对任意 $e\in E\left(G\right)$，$c\left(e\right)$ 只用于染边 $e$。又由断言6可得，对任意点 $v\in V\left(G\right)$，都有 $d_G\left(v\right)=2$，所以G是一个2-正则图。因此，对任意 $i\in \left\{1,2,\cdots ,\omega \left(G\right)\right\}$，$G_i$ 为圈。令 $\left|V\left(G_i\right)\right|=n_i$，不妨设 $G_i=\left[v_1,v_2,\cdots ,v_{n_i}\right]$。

断言9. 对任意 $v_j,v_{j+3}\in V\left(G_i\right)$，都有 $v_j,v_{j+3}$ 属于同一部集。

证明：显然， $n_i\ge 3$。假设存在 $v_j,v_{j+3}\in V\left(G_i\right)$，使得 $v_j,v_{j+3}$ 属于不同部集。现在我们考虑边 $v_j{v}_{j+3}$ 的颜色。注意对任意 $e\in E\left(G\right)$，$c\left(e\right)$ 只用于染边 $e$。所以 $c\left(v_j{v}_{j+1}\right),c\left(v_{j+1}{v}_{j+2}\right)$ 以及 $c\left(v_{j+2j+3}\right)$ 分别只用于染边 $v_j{v}_{j+1},v_{j+1}{v}_{j+2},v_{j+2}{v}_{j+3}$，因此， $c\left(v_j{v}_{j+3}\right)\notin \left\{c\left(v_j{v}_{j+1}\right),c\left(v_{j+1}{v}_{j+2}\right),c\left(v_{j+2}{v}_{j+3}\right)\right\}$。显然，此时存在一个彩虹子图 $C_4=\left[v_j,v_{j+1},v_{j+2},v_{j+3}\right]$，矛盾。断言9证明完毕。

由断言9可知， $n=0\left(\mathrm{mod}3\right)$ 且 $\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)=\frac{n}{3}$。根据归纳假设可知，对任意点 $v\in V\left(K_{n_1,n_2,\cdots ,n_m}\right)$，

都有

$\left|c\left(K_{n_1,n_2,\cdots ,n_m}-v\right)\right|\le AR\left(K_{n_1,n_2,\cdots ,n_m}-v,C_4\right)=n+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-3$.

因此，对任意点 $v\in V\left(K_{n_1,n_2,\cdots ,n_m}\right)$，都有

$\begin{array}{c}l\left(v\right)=\left|c\left(K_{n_1,n_2,\cdots ,n_m}\right)\right|-\left|c\left(K_{n_1,n_2,\cdots ,n_m}-v\right)\right|\\ \ge n+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-\left(n+\Gamma \left(K_{n_1,n_2,\cdots ,n_m}\right)-3\right)\\ =3\end{array}$

这与断言6矛盾。

综上所述，定理3.2证明完毕。

文章引用

余 婷,钟康云. 完全多部图中4-圈的Anti-Ramsey数
Anti-Ramsey Number of 4-Cycle in Complete Multipartite Graphs[J]. 应用数学进展, 2021, 10(07): 2378-2384. https://doi.org/10.12677/AAM.2021.107249

参考文献