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 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

Z.M. Jin

Zemin Jin

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

email: zeminjin@zjnu.cn

J.Q. Gu

Junqi Gu

Zhejiang Normal University

email: 3250066378@qq.com

Title:

Rainbow disjoint union of clique and matching in edge-colored complete graph

PDF

Source:

Discussiones Mathematicae Graph Theory 44(3) (2024) 953-970

Received: 2022-05-28 , Revised: 2022-11-09 , Accepted: 2022-11-12 , Available online: 2023-01-29 , https://doi.org/10.7151/dmgt.2483

Abstract:

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\cup tP_2$ in complete graphs. Also, we improve the bound and obtain the exact value of $AR(K_n,C_3\cup tP_2)$ for all $n\geq 2t+3$.

Keywords:

rainbow matching, anti-Ramsey number, clique

References:

  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, 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 $K_n$, 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
Close