Geodesic
Rainbow disjoint union of clique and matching in edge-colored complete graph
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 953-970 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Given an edge-coloring of a graph G, G is said to be rainbow if any two edges of G receive different colors. The anti-Ramsey number AR(G,H) is defined to be the maximum integer k such that there exists a k-edge-coloring of G avoiding rainbow copies of H. The anti-Ramsey number for graphs, especially matchings, have been studied in several graph classes. Gilboa and Roditty focused on the anti-Ramsey number of graphs with small components, especially including a matching. In this paper, we continue the work in this direct and determine the exact value of the anti-Ramsey number of K_4∪ tP_2 in complete graphs. Also, we improve the bound and obtain the exact value of AR(K_n,C_3∪ tP_2) for all n≥ 2t+3.
Keywords: rainbow matching, anti-Ramsey number, clique 
@article{DMGT_2024_44_3_a7,
     author = {Jin, Zemin and Gu, Junqi},
     title = {Rainbow disjoint union of clique and matching in edge-colored complete graph},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {953--970},
     year = {2024},
     volume = {44},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a7/}
}
TY  - JOUR
AU  - Jin, Zemin
AU  - Gu, Junqi
TI  - Rainbow disjoint union of clique and matching in edge-colored complete graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 953
EP  - 970
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a7/
LA  - en
ID  - DMGT_2024_44_3_a7
ER  - 
%0 Journal Article
%A Jin, Zemin
%A Gu, Junqi
%T Rainbow disjoint union of clique and matching in edge-colored complete graph
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 953-970
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a7/
%G en
%F DMGT_2024_44_3_a7
Jin, Zemin; Gu, Junqi. Rainbow disjoint union of clique and matching in edge-colored complete graph. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 953-970. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a7/

[1] N. Alon, On a conjecture of Erdős, Simonovits and Sós concerning anti-Ramsey theorems, J. Graph Theory 7 (1983) 91–94. https://doi.org/10.1002/jgt.3190070112

[2] A. Bialostocki, S. Gilboa and Y. Roditty, Anti-Ramsey numbers of small graphs, Ars Combin. 123 (2015) 41–53.

[3] G. Chen, Y.X. Lan and Z.X. Song, Planar anti-Ramsey numbers of matchings, Discrete Math. 342 (2019) 2106–2111. https://doi.org/10.1016/j.disc.2019.04.005

[4] H. Chen, X.L. Li and J.H. Tu, Complete solution for the rainbow numbers of matchings, Discrete Math. 309 (2009) 3370–3380. https://doi.org/10.1016/j.disc.2008.10.002

[5] P. Erdős, M. Simonovits and V.T. Sós, Anti-Ramsey theorems, in: Infinite and Finite Sets, Vol. II, A. Hajnal, R. Rado, and V.T. Sós (Ed(s)), (North-Holland, Amsterdam 1975) 633–643.

[6] P. Frankl and A. Kupavskii, Two problems on matchings in set families–-In the footsteps of Erdős and Kleitman, J. Combin. Theory, Ser. B 138 (2019) 286–313. https://doi.org/10.1016/j.jctb.2019.02.004

[7] S. Gilboa and Y. Roditty, Anti-Ramsey numbers of graphs with small connected components, Graphs Combin. 32 (2016) 649–662. https://doi.org/10.1007/s00373-015-1581-y

[8] R. Haas and M. Young, The anti-Ramsey number of perfect matching, Discrete Math. 312 (2012) 933–937. https://doi.org/10.1016/j.disc.2011.10.017

[9] S. Jahanbekam and D.B. West, Anti-Ramsey problems for t edge-disjoint rainbow spanning subgraphs: cycles, matchings, or trees, J. Graph Theory 82 (2016) 75–89. https://doi.org/10.1002/jgt.21888

[10] S. Jendrol', I. Schiermeyer and J.H. Tu, Rainbow numbers for matchings in plane triangulations, Discrete Math. 331 (2014) 158–164. https://doi.org/10.1016/j.disc.2014.05.012

[11] Y.X. Jia, M. Lu and Y. Zhang, Anti-Ramsey problems in complete bipartite graphs for t edge-disjoint rainbow spanning subgraphs: cycles and matchings, Graphs Combin. 35 (2019) 1011–1021. https://doi.org/10.1007/s00373-019-02053-y

[12] Z.M. Jin, Anti-Ramsey numbers for matchings in 3-regular bipartite graphs, Appl. Math. Comput. 292 (2017) 114–119. https://doi.org/10.1016/j.amc.2016.07.037

[13] Z.M. Jin, Anti-Ramsey number of matchings in a hypergraph, Discrete Math. 344(12) (2021) 112594. https://doi.org/10.1016/j.disc.2021.112594

[14] Z.M. Jin, H.W. Ma and R. Yu, Rainbow matchings in an edge-colored planar bipartite graph, Appl. Math. Comput. 432 (2022) 127356. https://doi.org/10.1016/j.amc.2022.127356

[15] Z.M. Jin and K. Ye, Rainbow number of matchings in planar graphs, Discrete Math. 341 (2018) 2846–2858. https://doi.org/10.1016/j.disc.2018.06.044

[16] Z.M. Jin, K.C. Ye, Y.F. Sun and H. Chen, Rainbow matchings in edge-colored complete split graphs, European J. Combin. 70 (2018) 297–316. https://doi.org/10.1016/j.ejc.2018.01.010

[17] X.L. Li, J.H. Tu and Z.M. Jin, Bipartite rainbow numbers of matchings, Discrete Math. 309 (2009) 2575–2578. https://doi.org/10.1016/j.disc.2008.05.011

[18] X.L. Li and Z.X. Xu, The rainbow number of matchings in regular bipartite graphs, Appl. Math. Lett. 22 (2009) 1525–1528. https://doi.org/10.1016/j.aml.2009.03.019

[19] J.J. Montellano-Ballesteros and V. Neumann-Lara, An anti-Ramsey theorem on cycles, Graphs Combin. 21 (2005) 343–354. https://doi.org/10.1007/s00373-005-0619-y

[20] Z.M. Qin, Y.X. Lan and Y.T. Shi, Improved bounds for rainbow numbers of matchings in plane triangulations, Discrete Math. 342 (2019) 221–225. https://doi.org/10.1016/j.disc.2018.09.031

[21] Z.M. Qin, Y.X. Lan, Y.T. Shi and J. Yue, Exact rainbow numbers for matchings in plane triangulations, Discrete Math. 344(4) (2021) 112301. https://doi.org/10.1016/j.disc.2021.112301

[22] L. Özkahya and M. Young, Anti-Ramsey number of matchings in hypergraphs, Discrete Math. 313 (2013) 2359–2364. https://doi.org/10.1016/j.disc.2013.06.015

[23] I. Schiermeyer, Rainbow numbers for matchings and complete graphs, Discrete Math. 286 (2004) 157–162. https://doi.org/10.1016/j.disc.2003.11.057

[24] M. Simonovits and V.T. Sós, On restricting colorings of Kn, Combinatorica 4 (1984) 101–110. https://doi.org/10.1007/BF02579162

[25] Y.S. Xue, E.F. Shan and L.Y. Kang, Anti-Ramsey number of matchings in r-partite r-uniform hypergraphs, Discrete Math. 345(4) (2022) 112782. https://doi.org/10.1016/j.disc.2021.112782