DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in press

Authors:

Q. Jie

Qing Jie

Zhejiang Normal University

email: 2782193314@qq.com

Z.M. Jin

Zemin Jin

Zhejiang Normal University, Jinhua, 321004, P.R. CHINA

email: zeminjin@zjnu.cn

0000-0002-9034-6018

Title:

Anti-Ramsey number of union of 5-path and matching

PDF

Source:

Discussiones Mathematicae Graph Theory

Received: 2024-06-28 , Revised: 2025-01-10 , Accepted: 2025-01-14 , Available online: 2025-02-06 , https://doi.org/10.7151/dmgt.2579

Abstract:

The anti-Ramsey number $AR(K_n, G)$ is defined as the maximum integer $k$ such that there is an edge coloring of $K_n$ using $k$ colors, in which there is no rainbow copy of $G$, namely, a copy of $G$ whose edges have distinct colors. In 2016, Gilboa and Roditty provided the upper and lower bounds of the anti-Ramsey number for $P_k\cup tP_2$ with $k\ge 5$. The problem on linear forests was considered in recent years. In this paper, we consider the case $k=5$ and we determine the exact value of the anti-Ramsey number $AR(K_n, P_5\cup tP_2)$ for $n\geq 2t+6$.

Keywords:

anti-Ramsey number, rainbow matching, disjoint union of \linebreak graphs

References:

  1. A. Bialostocki, S. Gilboa and Y. Roditty, Anti-Ramsey numbers of small graphs, Ars Combin. 123 (2015) 41–53.
  2. 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
  3. 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
  4. 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)), Colloq. Math. Soc. János Bolyai 10, (North-Holland, Amsterdam, 1975) 633–643.
  5. C.Q. Fang, E. Győri, M. Lu and J.M. Xiao, On the anti-Ramsey number of forests, Discrete Appl. Math. 291 (2021) 129–142.
    https://doi.org/10.1016/j.dam.2020.08.027
  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. Fujita, A. Kaneko, I. Schiermeyer and K. Suzuki, A rainbow $k$-matching in the complete graph with $r$ colors, Electron. J. Combin. 16(1) (2009) #R51.
    https://doi.org/10.37236/140
  8. 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
  9. M.Y. Guo, H.L. Lu and X. Peng, Anti-Ramsey number of matchings in $3$-uniform hypergraphs, SIAM J. Discrete Math. 37 (2023) 1970–1987.
    https://doi.org/10.1137/22M1503178
  10. 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
  11. M.L. He and Z.M. Jin, Rainbow short linear forests in edge-colored complete graph, Discrete Appl. Math. 361 (2025) 523–536.
    https://doi.org/10.1016/j.dam.2024.11.002
  12. 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
  13. S. Jendrol${'}$, On rainbow matchings in plane triangulations, Discrete Math. 342(12) (2019) 111624.
    https://doi.org/10.1016/j.disc.2019.111624
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. Z.M. Jin and J.Q. Gu, Rainbow disjoint union of clique and matching in edge-colored complete graph, Discuss. Math. Graph Theory 44 (2024) 953–970.
    https://doi.org/10.7151/dmgt.2483
  20. Z.M. Jin, Q. Jie and Z.X. Cao, Rainbow disjoint union of $P_4$ and a matching in complete graphs, Appl. Math. Comput. 474 (2024) 128679.
    https://doi.org/10.1016/j.amc.2024.128679
  21. Z.M. Jin, Y.F. Sun, S.H.F. Yan and Y.P. Zang, Extremal coloring for the anti-Ramsey problem of matchings in complete graphs, J. Comb. Optim. 34 (2017) 1012–1028.
    https://doi.org/10.1007/s10878-017-0125-1
  22. 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
  23. 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
  24. Z.M. Jin, R. Yu and Y.F. Sun, Anti-Ramsey number of matchings in outerplanar graphs, Discrete Appl. Math. 345 (2024) 125–135.
    https://doi.org/10.1016/j.dam.2023.11.049
  25. Z.M. Jin and Y.P. Zang, Anti-Ramsey coloring for matchings in complete bipartite graphs, J. Comb. Optim. 33 (2017) 1–12, 10.1007/s10878-015-9926-2.
  26. Z.M. Jin, W.J. Zhou, T. Yu and Y.F. Sun, Anti-Ramsey number for perfect matchings in $3$-regular bipartite graphs, Discrete Math. 347(7) (2024) 114011.
    https://doi.org/10.1016/j.disc.2024.114011
  27. X.L. Li, J.H. Tu and Z.M. Jin, Bipartite rainbow numbers of matchings, Discrete Math. 309 (2009) 2575–2578, 10.1016/j.disc.2008.05.011.
  28. X.L. Li and Z.X. Xu, The rainbow number of matchings in regular bipartite graphs, Appl. Math. Lett. 22 (2009) 1525–1528, 10.1016/j.aml.2009.03.019.
  29. 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
  30. Y.F. Pei, Y.X. Lan and H. He, Improved bounds for anti-Ramsey numbers of matchings in outer-planar graphs, Appl. Math. Comput. 418 (2022) 126843.
    https://doi.org/10.1016/j.amc.2021.126843
  31. 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
  32. 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
  33. I. Schiermeyer, Rainbow numbers for matchings and complete graphs, Discrete Math. 286) (2004) 157–162, 10.1016/j.disc.2003.11.057.
  34. T.Y. Xie and L.-T. Yuan, On the anti-Ramsey numbers of linear forests, Discrete Math. 343(12) (2020) 112130.
    https://doi.org/10.1016/j.disc.2020.112130
  35. 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
Close