Article in volume
Authors:
Title:
Rainbow disjoint union of clique and matching in edge-colored complete graph
PDFSource:
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:
- 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 - A. Bialostocki, S. Gilboa and Y. Roditty, Anti-Ramsey numbers of small graphs, Ars Combin. 123 (2015) 41–53.
- 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 - 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 - 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.
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - M. Simonovits and V.T. Sós, On restricting colorings of $K_n$, Combinatorica 4 (1984) 101–110.
https://doi.org/10.1007/BF02579162 - 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