2025/11/06 by Lu, Hongliang, Yang, Zixuan, Yuan, Feihong
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2511.04374
Let G be an edge-colored graph. We use e(G) and c(G) to denote the number of edges and colors in G, respectively. A subgraph H is called rainbow if c(H)=e(H). Li et al. (European J. Combin., 36 (2014), 453-459) proved that every edge-colored graph on n vertices with e(G)+c(G) ≥ n(n+1)/2 contains rainbow triangles. Later, Xu et al. (European J. Combin., 54 (2016), 193-200) generalized the previous results concerning rainbow triangles to rainbow cliques Kr, where r≥ 4. In this paper, we consider the existence of rainbow matchings of size k in general edge-colored graphs G under the condition of e(G)+c(G), and the condition in our result is tight.