论文标题
边缘色图中的大彩虹匹配
Large rainbow matchings in edge-colored graphs
论文作者
论文摘要
关于在适当的边缘色图中找到大彩虹匹配（没有两个边缘的颜色相同）的主题有很多研究，其中适当的边缘着色是边缘集的着色，因此不会出现相同的边缘。最近，Gao，Ramadurai，Wanless和Wormald证明，在具有$ Q $颜色的图形的每个适当边缘着色中，每种颜色至少出现$ q+o（q）$ times，总有每种颜色的彩虹匹配。我们通过同时放松两个条件来增强这一结果：（i）我们提高颜色数量并允许任何有限数量的颜色的条件，相反，请放置较弱的条件，要求最大的图形最多$ Q $，并且（ii）我们还放松了适当的着色条件，并要求颜色的每个颜色都构成了颜色。这种加强的方法可以解决一个自然的问题，灵感来自Gao，Ramadurai，Wanless和Wormald的言论。 作为此结果的应用，我们表明，对于$ 2Q+o（q）$颜色的每个适当的边缘着色，每种颜色至少出现$ Q $ times，总有大小$ q $的彩虹匹配。这可以看作是Barát，Gyárfás和Sárközy的猜想的渐近版本，限制在简单的图表上。我们还提供了一个结构，表明拥有$ Q+1美元的颜色是不够的，可以反驳Aharoni和Berger的猜想。作为我们技术的副产品，我们获得了新的渐近版本的Brualdi-ryser-stein猜想，这是Compinatorics中的核心开放问题之一。
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. Recently, Gao, Ramadurai, Wanless, and Wormald proved that in every proper edge coloring of a graph with $q$ colors where each color appears at least $q+o(q)$ times, there is always a rainbow matching using every color. We strengthen this result by simultaneously relaxing two 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 $q$, and (ii) we also relax the proper coloring condition and require that the graph induced by each of the colors have bounded degree. This strengthening resolves a natural question inspired by the remarks made by Gao, Ramadurai, Wanless, and Wormald. As an application of this result, we show that for every proper edge coloring of a graph with $2q+o(q)$ colors where each color appears at least $q$ times, there is always a rainbow matching of size $q$. This can be seen as an asymptotic version of a conjecture of Barát, Gyárfás, and Sárközy restricted on simple graphs. We also provide a construction showing that having $q+1$ colors is not enough, disproving a conjecture of Aharoni and Berger. As a by-product of our techniques, we obtain a new asymptotic version of the Brualdi--Ryser--Stein Conjecture, which is one of the central open questions in combinatorics.
