# Anti-Ramsey Numbers in Complete k-Partite Graphs

Authors: Jili Ding; Hong Bian; Haizheng Yu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The anti-Ramsey numberARG,H is the maximum number of colors in an edge-coloring of G such that G contains no rainbow subgraphs isomorphic to H. In this paper, we discuss the anti-Ramsey numbers ARKp1,p2,…,pk,Tn, ARKp1,p2,…,pk,ℳ, and ARKp1,p2,…,pk,C of Kp1,p2,…,pk, where Tn,ℳ,andC denote the family of all spanning trees, the family of all perfect matchings, and the family of all Hamilton cycles in Kp1,p2,…,pk, respectively.


---

## Body

## 1. Introduction

LetG be a graph, a k-edge-coloring of a graph G=V,E is a mapping c:E⟶C, where C is a set of colors, namely, C=1,2,…,k [1]. A subgraph H of an edge-colored graph G is rainbow if all of its edges have different colors. An edge-colored graph is called rainbow graph if all the colors on the edges are distinct. A representing subgraph in an edge-coloring of G is a spanning subgraph obtained by taking one edge of each color. The anti-Ramsey number ARG,H is the maximum number of colors in an edge-coloring of G with no rainbow copy of H. Rainbow coloring of graphs also has its application in practice. It comes from the secure communication of information between agencies of government. The anti-Ramsey number was introduced by Erdo¨s, Simonovits, and So´s in 1973 [2]. It has been shown that the anti-Ramsey number ARG,H is closely related to Tura´n number. The Tura´n number exn,H is the maximum number of edges in a graph G on n vertices which does not contain any subgraph isomorphic to H. Erdo¨s et al. conjectured that ARKn,Ck=nk−2/2+1/k−1+O1, for every fixed k≥3 [2]. The conjecture is proved completely for all k≥3 in [3] by Montellano-Ballesteros and Neumann-Lara. The anti-Ramsey numbers for some other special graph classes in complete graphs have also been studied, including independent cycles [4], stars [5], spanning trees [6], and matchings [7, 8]. The anti-Ramsey problems for rainbow matchings, cycles, and trees in complete bipartite graphs have been studied in [9–11]. Some other graphs were also considered as the host graphs in anti-Ramsey problems, such as hypergraphs [12], hypecubes [13], plane triangulations [14], and planar graphs [15].It is natural to consider that the anti-Ramsey problems for rainbow matchings, cycles, and trees in completek-partite graphs. In this paper, we are interested in the anti-Ramsey numbers for spanning trees, perfect matchings, and Hamilton cycles in complete k-partite graphs. A complete k-partite graph is a graph whose vertices can be partitioned into k different independent sets, and any two vertices from different independent sets are connected by an edge. A complete k-partite graph, with partitions S1,S2,…,Sk, k≥2, is denoted by Kp1,p2,…,pk, without loss of generality; in the following, we always assume that S1=p1,S2=p2,…,Sk=pk, p1≥p2≥…≥pk≥2, p1+p2+…+pk=∑i=1npi=n. If p1=p2=…=pk=1, G=Kk is a complete graph. Bialostocki and Voxman proved that ARKn,Tn=n−22+1, where Tn denotes the family of all spanning trees in Kn [6]. The maximum number of colors in an edge-coloring of Kn with no rainbow perfect matching (for even n) is n−32+2, when n≥14 [8].


## 2. Main Result

The family of all spanning trees inKp1,p2,…,pk is denoted by Tn. The maximum number of colors in an edge-coloring of Kp1,p2,…,pk not containing any rainbow spanning tree is denoted by ARKp1,p2,…,pk,Tn.Theorem 1.
IfS1=p1,S2=p2,…,Sk=pk, p1≥p2≥…≥pk≥2, k≥2, then(1)ARKp1,p2,…,pk,Tn≥∑1≤i<j≤kpipj−2∑i=2kpi+1,p1>p2,∑1≤i<j≤kpipj−2∑i=2kpi+2,p1=p2.Proof.
LetKp1,p2,…,pk be a complete k-partite graph with vertex set S1∪S2∪…∪Sk, k≥2, S1=p1,S2=p2,…,Sk=pk, p1≥p2≥…≥pk≥2.
The proof of the theorem is distinguished into the following two cases (see Figure1):Case 1:p1>p2.There is an edge-coloring ofKp1,p2,…,pk using ∑1≤i<j≤kpipj−2∑i=2kpi+1 colors such that Kp1,p2,…,pk does not contain any rainbow spanning tree Tn.Firstly, fix two verticesv1andv2 from S1 and color all edges incident with v1 and v2 by some color, say c1, that is, cv1ui=c1 and cv2ui=c1, for all vertices ui∈VKp1,p2,…,pk−S1. Since EKp1,p2,…,pk=∑1≤i<j≤kpipj, the number of remaining edges which are not colored is ∑1≤i<j≤kpipj−2∑i=2kpi. Then, color all other edges of Kp1,p2,…,pk using ∑1≤i<j≤kpipj−2∑i=2kpi colors such that each appears on one edge. Assume that there is a rainbow spanning tree Tn of Kp1,p2,…,pk in this coloring, and then the spanning tree Tn must contain two edges with the same color c1, one incident with v1 and the other incident with v2, a contradiction. Thus,(2)ARKp1,p2,…,pk,Tn≥∑1≤i<j≤kpipj−2∑i=2kpi+1.Case 2:p1=p2.
If we use∑1≤i<j≤kpipj−2∑i=2kpi+2 different colors to color the edges of Kp1,p2,…,pk, then the Kp1,p2,…,pk does not contain any rainbow spanning tree Tn.
Fix verticesv1 from S1 and u1 from S2. Firstly, color the edges incident with v1 and u1 by color c1, that is, cv1w1=c1, for all vertices w1∈VKp1,p2,…,pk−S1 and cu1w2=c1, for all vertices w2∈VKp1,p2,…,pk−S2, then color the remaining edges of Kp1,p2,…,pk using ∑1≤i<j≤kpipj−2∑i=2kpi+1 colors such that each appears on one edge, and the number of colors is ∑1≤i<j≤kpipj−2∑i=2kpi+2. Now, every spanning tree Tn of Kp1,p2,…,pk has at least two edges of the same color c1. Thus,(3)ARKp1,p2,…,pk,Tn≥∑1≤i<j≤kpipj−2∑i=2kpi+2.Figure 1
Two ways of coloring in case 1 and case 2.
(a)(b)Theorem 2.
IfS1=p1,S2=p2,…,Sk=pk, p1≥p2≥…≥pk≥2, k≥2, then(4)ARKp1,p2,…,pk,Tn≤∑1≤i<j≤kpipj−∑i=2kpi.Proof.
We consider an arbitrary edge-coloring ofKp1,p2,…,pk using ∑1≤i<j≤kpipj−∑i=2kpi+1 different colors. We only show that there is a spanning tree Tn of Kp1,p2,…,pk. We choose a representing subgraph G from Kp1,p2,…,pk with EG=∑1≤i<j≤kpipj−∑i=2kpi+1. Note that Kp1,p2,…,pk is disconnected by deleting at least ∑i=2kpi edges. Thus, G is connected. G contains a rainbow spanning tree Tn since every connected graph has a spanning tree.
The family of all Hamilton cycles inKp1,p2,…,pk is denoted by C. ARKp1,p2,…,pk,C is the maximum number of colors in an edge-coloring Kp1,p2,…,pk not containing any rainbow Hamilton cycle.
In order to prove our main result, we need the following lemma.Lemma 1.
(Dirac’s theorem, see [1]). If G is a graph on n≥3 vertices such that δG≥n/2, then G is Hamiltonian.Theorem 3.
LetKp1,p2,…,pk be a complete k-partite graph with p1≥p2≥…≥pk≥2 and k≥2; if ∑i=2kpi≥p1, then Kp1,p2,…,pk must have a Hamilton cycle.Proof.
By assumption and the structure ofKp1,p2,…,pk, it is clear that δKp1,p2,…,pk=∑i=2kpi, and according to Dirac’s Theorem, ∑i=2kpi≥VKp1,p2,…,pk/2=∑i=1kpi/2, Kp1,p2,…,pk have a Hamilton cycle. In fact, ∑i=2kpi≥∑i=1kpi/2, namely, ∑i=2kpi≥p1. The proof is finished.Theorem 4.
Ifp1≥p2≥…≥pk≥2, k≥2, ∑i=2kpi≥p1, then(5)ARKp1,p2,…,pk,C≥∑1≤i<j≤kpipj−∑i=2kpi+1.Proof.
By assumption and Theorem4, Kp1,p2,…,pk is clear Hamiltonian. Now, we show that there is an edge-coloring of Kp1,p2,…,pk using ∑1≤i<j≤kpipj−∑i=2kpi+1 colors such that Kp1,p2,…,pk does not contain rainbow Hamilton cycle. Firstly, fix any one vertex v from S1, color all the edges incident with v by color c1, and then color all other edges of Kp1,p2,…,pk using ∑1≤i<j≤kpipj−∑i=2kpi colors such that each appears on one edge. Note that every Hamilton cycle of Kp1,p2,…,pk must contain two edges incident with v, and the two edges have the same color c1. So, Kp1,p2,…,pk has no rainbow Hamilton cycle. Thus,(6)ARKp1,p2,…,pk,C≥∑1≤i<j≤kpipj−∑i=2kpi+1.
In order to prove the next main theorem, we need the following definition.
LetG be a k-partite graph with vertex set S1∪S2∪…∪Sk, if there are two vertices u∈Si and v∈Sj, i≠j, i,j∈1,2,…,k, uv∉EG, with dGu+dGv≥k−1p+1, then add an edge uv to EG. The closure of G is the graph obtained from G by repeating this step until there are no such pair of vertices, denoted by cG.Lemma 2.
(see [1]). G is a simple graph, and then G contains a Hamilton cycle if and only if its closure cG is Hamiltonian.Theorem 5.
LetG be a k-partite graph with S1=S2=…=Sk=p≥2. Suppose d1j,d2j,…,dpj are the vertex degrees of Sj of G, all in nondecreasing order, where 1≤j≤k,k≥2. If dij>i for each i≤k−1p/2, then G contains a Hamilton cycle.Proof.
By Lemma2, we only need to prove that cG is Hamiltonian. cG is a k-partite graph with vertex set S1∪S2∪…∪Sk. Suppose d1j,d2j,…,dpj are the vertex degrees of Sj of cG, all in nondecreasing order, where 1≤j≤k,k≥2,p≥2. dij≥dij for 1≤i≤p,1≤j≤k. To the contrary, suppose cG contains no Hamilton cycle, then cG is not a complete k-partite graph. Let uandv be two vertices in cG, u∈Si, v∈Sj, i≠j, uv∉EG, and dcGu+dcGv≤k−1p. If dcGu≤dcGv, set i=dcGu≤k−1p/2. k−1p−dcGv≥dcGu=i, cG contains at least k−1p−dcGv≥i vertices that are not adjacent to v, and each of which has degree at most dcGu=i. Thus, we can find some vertex w whose degree is at most dcGu=i in cG, which implies that i≥dcGw≥dGw, that is i≥dij≥dij, a contradiction.Theorem 6.
Ifp1≥p2≥…≥pk=p≥2, k≥2, then(7)ARKp1,p2,…,pk,C=kk−12p2−k−1p+1.Proof.
By Theorem4, we can easily prove the lower bound. We consider an arbitrary edge-coloring of Kp1,p2,…,pk using kk−1/2p2−k−1p+2 different colors, and we will find a rainbow Hamilton cycle in Kp1,p2,…,pk. We choose a representing subgraph G with EG=kk−1/2p2−k−1p+2. Let d1j,d2j,…,dpj be the vertex degrees of Sj of G, all in nondecreasing order. If dij>i for each i≤k−1p/2, 1≤j≤k, then G must contain a Hamilton cycle. If not, we assume that there exists i∗ such that di∗j≤i∗, i∗≤k−1p/2. Without loss of generality, we assume that d11≤d12≤…≤d1k and di∗1≤i∗. We have i∗⋅i∗+p−i∗k−1p+k−1k−2/2p2≥kk−1/2p2−k−1p+2=EG, that is, i∗2−pk−1i∗+pk−1−2≥0. Set fi=i2−pk−1i+pk−1−2=]i−pk−1−1i−1−1, f1=−1<0, f2=2−pk−1<0, fk−1p/2≤fpk−1−1=−1<0. We conclude that fi<0 for each 1≤i≤k−1p/2. Thus, we have dij>i for each i≤k−1p/2, 1≤j≤k. By Theorem 7, G must have a rainbow Hamilton cycle.
A matching in a graph is a set of nonadjacent edges. A perfect matchingM is a matching which saturates every vertex of the graph. The family of all perfect matchings Kp1,p2,…,pk is denoted by ℳ. ARKp1,p2,…,pk,ℳ is the maximum number of colors in an edge-coloring of Kp1,p2,…,pk not containing any rainbow perfect matching.
In [9], it has been shown that ARKm,n,kK2=mk−2+1, m≥n≥k≥3, which is the maximum numbers of colors in an edge-coloring of Km,n that contains no rainbow kK2. Now, we consider the maximum numbers of colors in an edge-coloring of Kp1,p2,…,pk not containing any rainbow perfect matching.
Tutte gives the sufficient and necessary condition of a graph with perfect matchings.Lemma 3.
(Tutte’s theorem, see [1]). A graph G has a perfect matching if and only if C0G−S≤S, for all S⊆VG, where C0G−S is the number of odd components of G−S.According to Tutte’s theorem, we give the following sufficient condition that completesk-partite graph Kp1,p2,…,pk have a perfect matching.Theorem 7.
Ifp1≥p2≥…≥pk≥1, k≥2, ∑i=1kpi is even and ∑i=2kpi≥p1, then the complete k-partite graph Kp1,p2,…,pk must have a perfect matching.Proof.
LetS be a subset of VKp1,p2,…,pk, and we consider the following three cases according to the cardinality of S.Case 1:0≤S<∑i=2kpi.Note thatKp1,p2,…,pk is disconnected by deleting at least ∑i=2kpi vertices. For 0≤S<∑i=2kpi, it is clear that Kp1,p2,…,pk−S is connected. If VKp1,p2,…,pk−S is even, then C0Kp1,p2,…,pk−S=0≤S, and if VKp1,p2,…,pk−S is odd, then C0Kp1,p2,…,pk−S=1, by assuming that ∑i=1kpi is even; thus, S is odd and S≥1 by the parity. So, C0Kp1,p2,…,pk−S≤S. By Lemma 3, Kp1,p2,…,pk has a perfect matching.Case 2:S=∑i=2kpi.IfS=∑i=2kpi, C0Kp1,p2,…,pk−S=p1≤∑i=2kpi=S, which meets Lemma 3, then Kp1,p2,…,pk has a perfect matching.Case 3:S>∑i=2kpi.
IfS>∑i=2kpi, C0Kp1,p2,…,pk−S=∑i=1kpi−S<p1<S, which also meets Lemma 9, then Kp1,p2,…,pk has a perfect matching.
Therefore, if∑i=1kpi is even and ∑i=2kpi≥p1, Kp1,p2,…,pk must have a perfect matching.
In this section, we consider the anti-Ramsey problem of perfect matching in completek-partite graph Kp1,p2,…,pk.Theorem 8.
Ifp1≥p2≥…≥pk≥2, k≥2, ∑i=1kpi is even and ∑i=2kpi≥p1, then(8)ARKp1,p2,…,pk,ℳ≥∑1≤i<j≤kpipj−2∑i=2kpi+1.Proof.
The known conditions clearly met thatKp1,p2,…,pk must have a perfect matching by Theorem 9. Now, we firstly show that there is an edge-coloring of Kp1,p2,…,pk using ∑1≤i<j≤kpipj−2∑i=2kpi+1 colors such that Kp1,p2,…,pk does not contain any rainbow perfect matching M. Fix two vertices v1andv2 from S1, color the edges incident with v1 and v2 by coloring c1, and color the remaining edges of Kp1,p2,…,pk using ∑1≤i<j≤kpipj−2∑i=2kpi colors such that each appears on one edge. It is clear that there is no rainbow perfect matching in Kp1,p2,…,pk. So, we have(9)ARKp1,p2,…,pk,ℳ≥∑1≤i<j≤kpipj−2∑i=2kpi+1.Theorem 9.
Ifp1≥p2≥…≥pk=p≥2, k≥2, kp is even, then(10)ARKp1,p2,…,pk,ℳ≤kk−12p2−k−1p+1.Proof.
We consider an arbitrary edge-coloring ofKp1,p2,…,pk using kk−1/2p2−k−1p+2 different colors, and we choose a representing subgraph G from Kp1,p2,…,pk. By the proof of Theorem 6, we know that G must have a rainbow Hamilton cycle C. Then, we can find a rainbow perfect matching from C since the number of vertices in Kp1,p2,…,pk is even. So,(11)ARKp1,p2,…,pk,ℳ<kk−12p2−k−1p+2.
The proof is completed.



---

*Source: 5136104-2020-09-07.xml*