2020/11/08 by Debsoumya Chakraborti, Chakraborti, Debsoumya, Po‐Shen Loh +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2011.04650
openalex publication_date 2020/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A subgraph of an edge-colored graph is called rainbow if all of its edges have distinct colors. There has been much research on the topic of finding a large rainbow matching in a properly edge-colored graph, where a proper edge-coloring is a coloring of the edge set such that no same-colored edges are incident. Gao, Ramadurai, Wanless, and Wormald proved that in every proper edge-coloring of a graph with n colors where each color appears at least n+o(n) times, there is always a rainbow matching using every color. We strengthen this result by simultaneously relaxing three conditions: (i) we lift the condition on the number of colors and allow any finite number of colors and instead, put a weaker condition requiring the maximum degree of the graph to be at most n, (ii) we relax the proper coloring condition and require that the graph induced by each of the colors have maximum degree o(n), and (iii) we work in a more general setting of multigraphs allowing edge multiplicities to be o(n). As an application of this result, we show that for every proper edge-coloring of a graph with 2n+o(n) colors where each color appears at least n times, there is always a rainbow matching of size n. Aharoni and Berger conjectured that 2n+o(n) can be replaced by n+1 in this statement. We dispute this conjecture with an explicit construction.