Rainbow triangles in edge-colored Kneser graphs

Rainbow triangles in edge-colored Kneser graphs

Applied Mathematics and Computation 365 (2020) 124724 Contents lists available at ScienceDirect Applied Mathematics and Computation journal homepage...

311KB Sizes 0 Downloads 15 Views

Applied Mathematics and Computation 365 (2020) 124724

Contents lists available at ScienceDirect

Applied Mathematics and Computation journal homepage: www.elsevier.com/locate/amc

Rainbow triangles in edge-colored Kneser graphs Zemin Jin a, Fang Wang a,∗, Huaping Wang b, Bihong Lv a a b

Department of Mathematics, Zhejiang Normal University, Jinhua 321004, PR China Department of Mathematics, Jiangxi Normal University, Nanchang, 330022, PR China

a r t i c l e

i n f o

Article history: Received 20 March 2019 Revised 13 August 2019 Accepted 2 September 2019 Available online 12 September 2019 MSC: 05C15 05C35 05C70

a b s t r a c t An edge-colored graph is called rainbow if all the edges have the different colors. The anti-Ramsey number AR(G, H) of a graph H in the graph G is defined to be the maximum number of colors in an edge-coloring of G which does not contain any rainbow H. In this paper, the existence of rainbow triangles in edge-colored Kneser graphs is studied. We give bounds for the anti-Ramsey number of triangles in Kneser graphs. Also, the anti-Ramsey number of triangles with an pendant edge is studied and the bounds are equal to bounds for triangles. © 2019 Elsevier Inc. All rights reserved.

Keywords: Kneser graph Rainbow triangle Anti-Ramsey number

1. Introduction An edge-colored graph is called rainbow if all the colors on its edges are distinct. The anti-Ramsey number of a graph ˝ et al. [4] in 1973, is defined to be the maximum number of colors in H in Kn , denoted by AR(Kn , H), introduced by Erdos an edge-coloring of Kn which does not contain any rainbow H. It has been shown that the anti-Ramsey number is closely related to the Turán number rather than the Ramsey number. The anti-Ramsey numbers of many graph classes, including cliques, paths, cycles, matchings etc., have been studied extensively and readers can refer to the surveys [5,6,20]. Although the anti-Ramsey number concerned the rainbow structures in complete graphs when it was introduced, it is natural to generalize the problem in other host graphs, in particular in complete bipartite graphs. During the last decade, researchers began to study the anti-Ramsey number in general graphs. Among them, the anti-Ramsey numbers of matchings and cycles are the most intensively studied. The anti-Ramsey problem for matching in complete graph and complete bipartite graphs was solved in [3,9,16,19,22,27]. Li and Xu [23] initialized the study of anti-Ramsey number in general graphs and considered the anti-Ramsey numbers of matchings in regular bipartite graphs. Jin [15] further improved the bound obtained in [23]. The authors [12,17,25,26] considered the anti-Ramsey number for matching in planar graphs. Recently, Jin et al. [18] determined the number for matchings in complete split graphs which covers the results in complete graphs. In this paper, we consider the anti-Ramsey number of cycles. This has been solved in complete graphs, see [1,4,14,24]. Axenovich et al. [2] determined the anti-Ramsey number of cycles in complete bipartite graphs. During recent years, the anti-Ramsey problem for cycles in other host graphs draw much attention. Gorgol [7,8] considered the anti-Ramsey number ∗

Corresponding author. E-mail addresses: [email protected] (Z. Jin), [email protected] (F. Wang).

https://doi.org/10.1016/j.amc.2019.124724 0 096-30 03/© 2019 Elsevier Inc. All rights reserved.

2

Z. Jin, F. Wang and H. Wang et al. / Applied Mathematics and Computation 365 (2020) 124724

ˇ for triangles and triangles with pendant edges. Hornák et al. [10] considered the anti-Ramsey number for cycles in plane triangulations. They determined the exact value for triangles and obtained lower and upper bounds for cycles of order at least four. Recently, Lan et al. [21] improved the upper bound for cycles of order at least five. Interestingly, the authors [11,13] studied the anti-Ramsey numbers for t edge-disjoint subgraphs including cycles. Here we aim to study the problem for triangles in Kneser graphs. The Kneser graph KGn,k on the set [n] = {1, 2, . . . , n} is defined the graph with vertices k-subsets of [n], where two vertices are adjacent if and only if the corresponding k-subsets are disjoint. Denote by c(G) the set of colors in an edge-colored graph G. Given an edge-colored Kneser graph KGn,k , denote by l(v) the set of colors only appearing at the vertex v ∈ KGn, k , namely, l (v ) = c (KGn,k )\c (KGn,k − v ). 2. Rainbow triangles in KGn,k For convenience, denote by {vB |B is a k-element subset of the set [n]} the set of the Kneser graph KGn,k . If B = {i} ∪ T , where i ∈ [n], T is a (k − 1 )-element subset of the set [n]ࢨ{i}, we denote by v(i, T) the vertex vB . Theorem 2.1. AR(KG3k,k , C3 ) = Proof. Lower bound

3k−12k k−1

k

.



First we construct an edge-coloring ψ 1 of KG3k,k without rainbow C3 . Take a subgraph KG3k−1,k of KG3k,k on the set [3k − 1]. Clearly, KG3k−1,k does not contain C3 . Color all the edges of KG3k−1,k by distinct colors. Then color the two edges v(3k,T ) vB1 and v(3k,T ) vB2 by a same new color, where T is a (k − 1 )-element subset of [3k − 1], B1 is a k-element subset of [3k − 1] \ T , B2 = [3k − 1] \ {T ∪ B1 }. Notice that the vertices v(3k,T ) , vB1 , vB2 induce a triangle. It is easy to see that there are



2k

1 3k−1 2 k−1

k triangles in KG3k,k and all of them are edge disjoint. So there is not any rainbow triangle in the coloring ψ 1 and we can see that the number of colors in ψ 1 is





1 3k − 1 2 k



2k − 1 k



 

1 3k − 1 + 2 k−1



2k k



 

3k − 1 k−1

=

 

2k . k

−1 2k This implies that AR(KG3k,k , C3 ) ≥ 3kk−1 k . Upper bound 3k−12k Let q(3k ) = k−1 k + 1. We only need to show that any q(3k)-edge-coloring of KG3k,k contains a rainbow triangle. Let c be a q(3k)-edge-coloring of KG3k,k . On the contrary, we assume that c doesn’t contain any rainbow triangle. We take a subgraph KG3k−1,k of KG3k,k on the set [3k − 1]. Clearly, KG3k−1,k has no any triangle. Then we have that



|c(KG3k−1,k )| ≤ |E (KG3k−1,k )| =



1 3k − 1 2 k



2k − 1 . k





−1 For each vertex v(3k,Tt ) ∈ V (KG3k,k ), where Tt , t = 1, 2, . . . , 3kk−1 is a (k − 1 )-element subset of the set [3k − 1], we have the following claim. 2k−1 3k−1 Claim |l (v(3k,Tt ) )| ≤ k−1 , t = 1, 2, . . . , k−1 . Proof of Claim  −1  −1 Assume that |l (v(3k,Tt ) )| ≥ 2kk−1 + 1 for some Tt . There exists a vertex set S of order |S| = 2kk−1 + 1 which is adjacent to v3k,Tt in KG3k,k . Moreover, all the colors of these edges between v3k,Tt and S are distinct and belong to l (v(3k,Tt ) ). Then we have that S ⊆ V(KG2k,k ), where KG2k,k is a Kneser graph on the set [3k − 1] \ Tt . By the Erdos-Ko-Rado theorem,





−1 the independence number of the KG2k,k is 2kk−1 . Then there exists two vertices x, y in S which are adjacent. So we get a triangle xyv(3k,Tt ) x in KG3k,k . Clearly, c (xy ) ∈ / l (v(3k,Tt ) ). Then xyv3k,Tt x is a rainbow triangle, a contradiction. Hence,  −1 |l (v(3k,Tt ) )| ≤ 2kk−1 . This completes the proof of the claim.  Hence from the claim above we have

q(3k ) = |c (KG3k,k )| = |c (KG3k−1,k )| +





1 3k − 1 ≤ 2 k



=

3k−1 ( k−1 )

|l (v(3k,Tt ) )|



2k − 1 k

 

3k − 1 k−1

t=1

 +



3k − 1 k−1



2k − 1 k−1

2k , k

a contradiction. This completes the proof of the theorem.  Now we consider the anti-Ramsey number of triangles in the Kneser graph KGn,k . First we consider the lower bound by constructing an edge-coloring of the Kneser graph KGn,k for n = 3km which does not contain any rainbow triangle.

Z. Jin, F. Wang and H. Wang et al. / Applied Mathematics and Computation 365 (2020) 124724

Theorem 2.2. Let n = 3km + t, 0 ≤ t ≤ 3k − 1. Then

AR(KGn,k , C3 ) ≥

 n  3k − 12k 3k

where ε = 1 if t = 0, and ε =

t  k

k−1

k

  3k k





3

 

+1 +

n k

− ε,

if t = 0.

Proof. Below we construct an edge-coloring ψ which does not contain rainbow triangle. We construct the edge coloring as follows. Let X1 , X2 , . . . , Xm ⊆ [3km] be the m disjoint sets of order 3k and let X = [n]\[3km]. Take m Kneser subgraphs G1 , G2 , . . . , Gm of KGn,k on the sets X1 , X2 , . . . , Xm , respectively. All of them are isomorphic to KG3k,k . Color all these subgraphs by ψ 1 given in Theorem 2.1 with the disjoint color sets. Color all the edges of the Kneser graph Gm+1 = KGn−3km,k on the set X by distinct new colors.     Let V (G ) = V (G1 ) ∪ V (G2 ) ∪ . . . ∪ V (Gm ) ∪ V (Gm+1 ), A = V (KGn,k )\V (G ) and it is clear that |A| = nk − m 3kk − kt . Notice that any two vertices from Gi and Gj , i = j, are adjacent in KGn,k and so KGn,k [A] is connected. We order the vertices of A and color the edges of KGn,k [A] lexically with new colors, i.e., the edge uv colored by the minimum order of u, v ∈ A. Then we order the graphs G1 , G2 , . . . , Gm , Gm+1 and KGn,k [A], and color the all edges between these graphs lexically with new colors. This completes the edge-coloring ψ of KGn,k . It is easy to see that there is not any rainbow triangle and we can see that the number of colors in ψ is (1) m|c (ψ1 )| + |E (Gm+1 )| + (|A| − 1 ) + m + 1, if t > 0, i.e.,



 

3k − 1 m k−1 i.e.,

2k k

  n k

+

 n  3k − 12k 3k

k−1

k



 

 

3k −m k



t k

 



 

3k k

+ m,

n k

+1 +

  −

t . k

(2) m|c (ψ1 )| + (|A| − 1 ) + m, if t = 0, i.e.,



m i.e.,

 

3k − 1 k−1

2k k

 

+

n k

 n  3k − 12k 3k

k−1

k

 

−m

3k k

  −

3k k

+ m − 1,



  n k

+1 +

− 1.

Hence we are done and this completes the proof of the result. For convenience, let q(n ) =

3k−12k k−1

k

+2+



  n  i−1 i−k−1 i=3k+1

k−1

k−1

− 1 for n ≥ 3k + 1 and let q(3k ) =

3k−12k k−1

k

+ 1.

Theorem 2.3. For n ≥ 3k, AR(KGn,k , C3 ) ≤ q(n ) − 1. Proof. We now show that any q(n)-edge-coloring of KGn,k contains a rainbow C3 . We prove the result by the induction on n. It follows from Theorem 2.1 that the theorem holds for n = 3k. Assume that the theorem holds for the Kneser graph KGn−1,k . Now we consider the Kneser graph KGn,k , n > 3k. Let c be a q(n)-edge-coloring of KGn,k . We need to show that c contains a rainbow triangle. On the contrary, assume that c does not contain any rainbow triangle. Take a Kneser subgraph KGn−1,k of KGn,k on the set [n − 1]. Clearly, the graph KGn−1,k does not contain any rainbow triangle. Then by the induction hypothesis, we have that |c (KGn−1,k )| ≤ q(n − 1 ) − 1. For each vertex v(n,Tt ) , where Tt , t = 1, 2, . . . ,

n−1 k−1

is one of (k − 1 )-element subsets of [n − 1], we have the following claim.









−1 n−1 Claim |l (v(n,Tt ) )| ≤ n−k k−1 , t = 1, 2, . . . , k−1 . Proof of Claim  −1  −1 Assume that |l (v(n,Tt ) )| ≥ n−k + 1 for some Tt . There exists a vertex set S of order |S| = n−k + 1 which is adjacent k−1 k−1 to v(n,Tt ) in KGn,k . Moreover, all the colors of these edges between v(n,Tt ) and S are distinct and belong to l (v(n,Tt ) ). Then we have that the set S is a set of vertices in the Kneser graph V (KGn−k,k ) on the set [n − 1] \ Tt . By the Erdos-Ko-Rado theorem,

the independence number of KGn−k,k is

n−k−1 k−1

. Then there exists two vertices x, y in S which are adjacent. So we get a

triangle xyv(n,Tt ) x. Clearly, c (xy ) ∈ / l (v(n,Tt ) ). Then xyv(n,Tt ) x is a rainbow triangle, a contradiction. Hence, |l (v(n,Tt ) )| ≤ This completes the proof of the claim.  So we have the following recurrence relation

q(n ) = |c (KGn,k )|

n−k−1 k−1

.

4

Z. Jin, F. Wang and H. Wang et al. / Applied Mathematics and Computation 365 (2020) 124724

= |c (KGn−1,k )| +

n−1 ( k−1 )

|l (v(n,Tt ) )|

t=1

 ≤ q (n − 1 ) − 1 +





n−1 k−1



n−k−1 , k−1

 

−1 2k with q(3k ) = 3kk−1 k + 1. Relying on the recurrence relation above, we have that



q (n ) ≤

 

3k − 1 k−1

2k k



n 

+1+

i=3k+1



i−1 k−1





i−k−1 k−1

−1 ,



a contradiction. This completes the proof of the theorem. 3. Rainbow triangles with a pendant edge in KGn,k

We denote by C3+ the triangle with a pendant edge. We have the following results.

3k−12k

Theorem 3.1. AR(KG3k,k , C3+ ) = AR(KG3k,k , C3 ) =

k−1

k

= q ( 3k ).

Proof. Certainly AR(KG3k,k , C3+ ) ≥ AR(KG3k,k , C3 ). We only need to show the opposite inequality. Now we show that any q(3k)-edge-coloring of KG3k,k contains a rainbow C3+ . Let c be a q(3k)-edge-coloring of KG3k,k . On the contrary, we assume that c doesn’t contain any rainbow C3+ .





−1 Denote by Tt , t = 1, 2, . . . , 3kk−1 the (k − 1 )-element subsets of [3k − 1]. By Theorem 2.1, we have that c contains a rainbow triangle and let v(3k,T1 ) be a vertex of a rainbow triangle. Take a subgraph KG3k−1,k of KG3k,k on the set [3k − 1]. Clearly, KG3k−1,k has no any C3+ . Then we have that



|c(KG3k−1,k )| ≤ |E (KG3k−1,k )| =



1 3k − 1 2 k



2k − 1 . k

For each vertex v(3k,Tt ) ∈ V (KG3k,k ), we have the following claims. Claim 1. |l (v(3k,T1 ) )| ≤ 2. This is obviously, since otherwise we can find a rainbow C3+ easily which leads to a contradiction.









−1 −1 Claim 2. |l (v(3k,Tt ) )| ≤ 2kk−1 for t = 2, 3, . . . , 3kk−1 . Proof of Claim 2 If the vertex v(3k,Tt ) belongs to a rainbow triangle, then we have that |l (v(3k,Tt ) )| ≤ 2 and the claim holds clearly. So

assume that the vertex v(3k,Tt ) doesn’t belong to any rainbow triangle. Suppose that |l (v(3k,Tt ) )| ≥

2k−1

2k−1 k−1

+ 1 for some Tt .

There exists a vertex set S of order |S| = k−1 + 1 which is adjacent to v(3k,Tt ) in KG3k,k . Moreover, all the colors of these edges between v(3k,Tt ) and S are distinct and belong to l (v(3k,Tt ) ). Then we have that S ⊆ V(KG2k,k ), where KG2k,k is a Kneser





−1 graph on the set [3k − 1] \ Tt . By the Erdos-Ko-Rado theorem, the independence number of the KG2k,k is 2kk−1 . Then there exist two vertices x, y in S which are adjacent. So we get a triangle xyv(3k,Tt ) x in KG3k,k . Clearly, c (xy ) ∈ / l (v(3k,Tt ) ). Then xyv(3k,Tt ) x is a rainbow triangle, i.e., the vertex v(3k,Tt ) belongs to a rainbow triangle, a contradiction. Hence, |l (v(3k,Tt ) )| ≤

2k−1 k−1

. This completes the proof of the claim.



Hence from the claims above we have

q(3k ) = |c (KG3k,k )| = |c (KG3k−1,k )| +





1 3k − 1 ≤ 2 k



=

3k−1 ( k−1 )

t=1

3k − 1 k−1



2k − 1 k

  2k k

|l (v(3k,Tt ) )| +









3k − 1 k−1



2k − 1 k−1

 −1



2k − 1 k−1

+2

+ 2,

a contradiction. This completes the proof of the theorem.  Now we consider the anti-Ramsey number of triangles with pendant edges in the Kneser graph KGn,k . Certainly AR(KGn,k , C3+ ) ≥ AR(KGn,k , C3 ). So we only have to show the upper bound for the Kneser graph KGn,k .

Z. Jin, F. Wang and H. Wang et al. / Applied Mathematics and Computation 365 (2020) 124724

Theorem 3.2. For n ≥ 3k, AR(KGn,k , C3+ ) ≤ q(n ) − 1.

3k−12k

Proof. Notice that q(n ) =

k−1

+2+

k



n

i−k−1

i−1 k−1

i=3k+1

k−1

− 1 for n ≥ 3k + 1 and q(3k ) =

5

3k−12k k−1

k

+ 1. We now show

that any q(n)-edge-coloring of KGn,k contains a rainbow C3+ . We prove the result by the induction on n. It follows from Theorem 3.1 that the theorem holds for n = 3k. Now we consider the Kneser graph KGn,k , n > 3k. Let c be a q(n)-edge-coloring of KGn,k . We need to show that c contains a rainbow C3+ . On the contrary, assume that c does not contain any rainbow C3+ .





−1 Denote by Tt , t = 1, 2, . . . , nk−1 the (k − 1 )-element subsets of [n − 1]. By the Theorem 2.3, we have that c contains a rainbow triangle and let v(n,T1 ) be a vertex of a rainbow triangle. Take a Kneser subgraph KGn−1,k of KGn,k on the set [n − 1]. Clearly, the graph KGn−1,k does not contain any rainbow C3+ . Then by the induction hypothesis, we have that |c (KGn−1,k )| ≤ q(n − 1 ) − 1. For each vertex v(n,Tt ) , we have the following claims. Claim 1. |l (v(n,T1 ) )| ≤ 2. This is obviously, since otherwise we can find a rainbow C3+ easily which leads to a contradiction.









−1 n−1 Claim 2. |l (v(n,Tt ) )| ≤ n−k k−1 , for t = 2, 3, . . . , k−1 . Proof of Claim 2 If the vertex v(n,Tt ) belongs to a rainbow triangle, then from Claim 1 we have that |l (v(n,Tt ) )| ≤ 2. So assume that the





−1 vertex v(n,Tt ) doesn’t belong to any rainbow triangle. Suppose that |l (v(n,Tt ) )| ≥ n−k + 1 for some t ≥ 2. There exists a k−1 n−k−1 vertex set S of order |S| = k−1 + 1 which is adjacent to v(n,Tt ) in KGn,k . Moreover, all the colors of these edges between v(n,Tt ) and S are distinct and belong to l (v(n,Tt ) ). Then we have that the set S is a set of vertices in the Kneser graph KGn−k,k





−1 on the set [n − 1] \ Tt . By the Erdos-Ko-Rado theorem, the independence number of KGn−k,k is n−k k−1 . Then there exists two vertices x, y in S which are adjacent. So we get a triangle xyv(n,Tt ) x. Clearly, c (xy ) ∈ / l (v(n,Tt ) ). Then xyv(n,Tt ) x is a rainbow

triangle. So v(n,Tt ) belongs to a rainbow triangle, a contradiction. Hence, |l (v(n,Tt ) )| ≤ claim. 

n−k−1 k−1

. This completes the proof of the

So we have the following recurrence relation

q(n ) = |c (KGn,k )| = |c (KGn−1,k )| +

n−1 ( k−1 )

l (v(n,Tt ) )

t=1

 ≤ q (n − 1 ) − 1 +

 = q (n − 1 ) +



 



n−1 k−1

 −1



n−1 k−1



n−k−1 k−1



n−k−1 k−1

+2





n−k−1 k−1



−1 2k with q(3k ) = 3kk−1 k + 1. Relying on the recurrence relation above, we have that



q (n ) ≤

 

3k − 1 k−1

2k k

+1+

n  i=3k+1





i−1 k−1

+ 1,



i−k−1 k−1

a contradiction. This completes the proof of the theorem.

 −



i−k−1 k−1

+1 ,



Acknowledgment This work was supported by National Natural Science Foundation of China (11571320 and 11671366) and Zhejiang Provincial Natural Science Foundation (LY19A010018). The authors are very grateful to the referees for helpful comments and suggestions. References [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

˝ Simonovits and Sós concerning anti-ramsey theorems, J. Graph Theory 1 (1983) 91–94. N. Alon, On a conjecture of Erdos, M. Axenovich, T. Jiang, A. Kündgen, Bipartite anti-ramsey numbers of cycles, J. Graph Theory 47 (2004) 9–28. H. Chen, X.L. Li, J.H. Tu, Complete solution for the rainbow numbers of matchings, Discrete Math. 309 (2009) 3370–3380. ˝ , M. Simonovits, V.T. Sós, Anti-ramsey theorems, in: Colloq. Math. Soc. Janos Bolyai. Vol.10, in: Infinite and Finite Sets, Keszthely, Hungary, P. Erdos 1973, pp. 657–665. S. Fujita, C. Magnant, K. Ozeki, Rainbow generalizations of ramsey theory: a survey, Graphs Combin. 26 (2010) 1–30. S. Fujita, C. Magnant, K. Ozeki, Rainbow generalizations of ramsey theory - a dynamic survey, Theory Appl. Graphs 0 (1) (2014). I. Gorgol, Rainbow numbers for cycles with pendant edges, Graphs Combin. 24 (2008) 327–331. I. Gorgol, Anti-Ramsey numbers in complete split graphs, Discrete Math. 339 (7) (2016) 1944–1949. R. Haas, M. Young, The anti-ramsey number of perfect matching, Discrete Math. 312 (5) (2012) 933–937. ˇ , S. Jendrol’, I. Schiermeyer, R. Soták, Rainbow numbers for cycles in plane triangulations, J. Graph Theory 78 (2015) 248–257. M. Hornák

6

Z. Jin, F. Wang and H. Wang et al. / Applied Mathematics and Computation 365 (2020) 124724

[11] S. Jahanbekam, D.B. West, Anti-ramsey problems for t edge-disjoint rainbow spanning subgraphs: cycles, matchings, or trees, J. Graph Theory 82 (1) (2016) 75–89. [12] S. Jendrol’, I. Schiermeyer, J.H. Tu, Rainbow numbers for matchings in plane triangulations, Discrete Math. 331 (28) (2014) 158–164. [13] Y. Jia, M. Lu, Y. Zhang, Anti-Ramsey problems in complete bipartite graphs for t edge-disjoint rainbow spanning subgraphs: cycles and matchings, Graphs Combin. (2019), doi:10.10 07/s0 0373- 019- 02053- y. ˝ [14] T. Jiang, D.B. West, On the Erdos-Simonovits-Sós conjecture on the anti-ramsey number of a cycle, Combin. Probab. Comput. 12 (2003) 585–598. [15] Z.M. Jin, Anti-ramsey numbers for matchings in 3-regular bipartite graphs, Appl. Math. Comput. 292 (2017) 114–119. [16] Z.M. Jin, Y.F. Sun, S.H.F. Yan, Y.P. Zang, Extremal coloring for the anti-Ramsey problem of matchings in complete graphs, J. Comb. Optim. 34 (2017) 1012–1028. [17] Z.M. Jin, K. Ye, Rainbow number of matchings in planar graphs, Discrete Math. 341 (2018) 2846–2858. [18] Z.M. Jin, K.C. Ye, Y.F. Sun, H. Chen, Rainbow matchings in edge-colored complete split graphs, European J. Combin. 70 (2018) 297–316. [19] Z.M. Jin, Y.P. Zang, Anti-Ramsey coloring for matchings in complete bipartite graphs, J. Comb. Optim. 33 (2017) 1–12. [20] M. Kano, X.L. Li, Monochromatic and heterochromatic subgraphs in edge-colored graphs - a survey, Graphs Combin. 24 (2008) 237–263. [21] Y.X. Lan, Y.T. Shi, Z.X. Song, Planar anti-ramsey numbers for paths and cycles, 2019, Submitted. arXiv:1709.00970. [22] X.L. Li, J.H. Tu, Z.M. Jin, Bipartite rainbow numbers of matchings, Discrete Math. 309 (2009) 2575–2578. [23] X.L. Li, Z.X. Xu, The rainbow number of matchings in regular bipartite graphs, Appl. Math. Lett. 22 (2009) 1525–1528. [24] J.J. Montellano-Ballesteros, V. Neumann-Lara, An anti-ramsey theorem on cycles, Graphs Combin. 21 (2005) 343–354. [25] Z. Qin, Y. Lan, Y. Shi, Improved bounds for rainbow numbers of matchings in plane triangulations, Discrete Math. 342 (2019) 221–225. [26] Z. Qin, Y. Lan, Y. Shi, J. Yue, Exact rainbow numbers for matchings in plane triangulations, arXiv:1903.00717. [27] I. Schiermeyer, Rainbow numbers for matchings and complete graphs, Discrete Math. 286 (2004) 157–162.