اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدBadges and rainbow matchings
242
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Drisko proved that $2n-1$ matchings of size $n$ in a bipartite graph have a rainbow matching of size $n$. For general graphs it is conjectured that $2n$ matchings suffice for this purpose (and that $2n-1$ matchings suffice when $n$ is even). The known graphs showing sharpness of this conjecture for $n$ even are called badges. We improve the previously best known bound from $3n-2$ to $3n-3$, using a new line of proof that involves analysis of the appearance of badges. We also prove a cooperative generalization: for $t>0$ and $n geq 3$, any $3n-4+t$ sets of edges, the union of every $t$ of which contains a matching of size $n$, have a rainbow matching of size $n$.
قيم البحث
اقرأ أيضاً
Grinblat (2002) asks the following question in the context of algebras of sets: What is the smallest number $mathfrak v = mathfrak v(n)$ such that, if $A_1, ldots, A_n$ are $n$ equivalence relations on a common finite ground set $X$, such that for ea
ch $i$ there are at least $mathfrak v$ elements of $X$ that belong to $A_i$-equivalence classes of size larger than $1$, then $X$ has a rainbow matching---a set of $2n$ distinct elements $a_1, b_1, ldots, a_n, b_n$, such that $a_i$ is $A_i$-equivalent to $b_i$ for each $i$? Grinblat has shown that $mathfrak v(n) le 10n/3 + O(sqrt{n})$. He asks whether $mathfrak v(n) = 3n-2$ for all $nge 4$. In this paper we improve the upper bound (for all large enough $n$) to $mathfrak v(n) le 16n/5 + O(1)$.
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
hings in graphs, made by Aharoni and Berger and others.
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 i
ncident. 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.
Given two graphs $G$ and $H$, the {it rainbow number} $rb(G,H)$ for $H$ with respect to $G$ is defined as the minimum number $k$ such that any $k$-edge-coloring of $G$ contains a rainbow $H$, i.e., a copy of $H$, all of its edges have different color
s. Denote by $M_t$ a matching of size $t$ and $mathcal {T}_n$ the class of all plane triangulations of order $n$, respectively. Jendrol, Schiermeyer and Tu initiated to investigate the rainbow numbers for matchings in plane triangulations, and proved some bounds for the value of $rb({mathcal {T}_n},M_t)$. Chen, Lan and Song proved that $2n+3t-14 le rb(mathcal {T}_n, M_t)le 2n+4t-13$ for all $nge 3t-6$ and $t ge 6$. In this paper, we determine the exact values of $rb({mathcal {T}_n},M_t)$ for large $n$, namely, $rb({mathcal {T}_n},M_t)=2n+3t-14$ for all $n ge 9t+3$ and $tge 7$.
Let $k>1$, and let $mathcal{F}$ be a family of $2n+k-3$ non-empty sets of edges in a bipartite graph. If the union of every $k$ members of $mathcal{F}$ contains a matching of size $n$, then there exists an $mathcal{F}$-rainbow matching of size $n$. U
pon replacing $2n+k-3$ by $2n+k-2$, the result can be proved both topologically and by a relatively simple combinatorial argument. The main effort is in gaining the last $1$, which makes the result sharp.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
