ﻻ يوجد ملخص باللغة العربية
There has been much research on the topic of finding a large rainbow matching (with no two edges having the same color) 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. Barat, Gyarfas, and Sarkozy conjectured that in every proper edge coloring of a multigraph (with parallel edges allowed, but not loops) with $2q$ colors where each color appears at least $q$ times, there is always a rainbow matching of size $q$. Recently, Aharoni, Berger, Chudnovsky, Howard, and Seymour proved a relaxation of the conjecture with $3q-2$ colors. Our main result proves that $2q + o(q)$ colors are enough if the graph is simple, confirming the conjecture asymptotically for simple graphs. This question restricted to simple graphs was considered before by Aharoni and Berger. We also disprove one of their conjectures regarding the lower bound on the number of colors one needs in the conjecture of Barat, Gyarfas, and Sarkozy for the class of simple graphs. Our methods are inspired by the randomized algorithm proposed by Gao, Ramadurai, Wanless, and Wormald to find a rainbow matching of size $q$ in a graph that is properly edge-colored with $q$ colors, where each color class contains $q + o(q)$ edges. We consider a modified version of their algorithm, with which we are able to prove a generalization of their statement with a slightly better error term in $o(q)$. As a by-product of our techniques, we obtain a new asymptotic version of the Brualdi-Ryser-Stein Conjecture.
A rainbow matching in an edge-colored graph is a matching in which no two edges have the same color. The color degree of a vertex v is the number of different colors on edges incident to v. Kritschgau [Electron. J. Combin. 27(2020)] studied the exist
Let $G$ be a graph of order $n$ with an edge-coloring $c$, and let $delta^c(G)$ denote the minimum color-degree of $G$. A subgraph $F$ of $G$ is called rainbow if any two edges of $F$ have distinct colors. There have been a lot results in the existin
Let $G = (V, E)$ be an $n$-vertex edge-colored graph. In 2013, H. Li proved that if every vertex $v in V$ is incident to at least $(n+1)/2$ distinctly colored edges, then $G$ admits a rainbow triangle. We prove that the same hypothesis ensures a rain
Let $G$ be a graph of order $n$ with an edge-coloring $c$, and let $delta^c(G)$ denote the minimum color degree of $G$. A subgraph $F$ of $G$ is called rainbow if all edges of $F$ have pairwise distinct colors. There have been a lot results on rainbo
A graph $G$ whose edges are coloured (not necessarily properly) contains a full rainbow matching if there is a matching $M$ that contains exactly one edge of each colour. We refute several conjectures on matchings in hypergraphs and full rainbow matc