No Arabic abstract
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 whose edges have different colors. Denote by $kK_2$ a matching of size $k$ and $mathcal {T}_n$ the class of all plane triangulations of order $n$, respectively. In [S. Jendrol$$, I. Schiermeyer and J. Tu, Rainbow numbers for matchings in plane triangulations, Discrete Math. 331(2014), 158--164], the authors determined the exact values of $rb(mathcal {T}_n, kK_2)$ for $2leq k le 4$ and proved that $2n+2k-9 le rb(mathcal {T}_n, kK_2) le 2n+2k-7+2binom{2k-2}{3}$ for $k ge 5$. In this paper, we improve the upper bounds and prove that $rb(mathcal {T}_n, kK_2)le 2n+6k-16$ for $n ge 2k$ and $kge 5$. Especially, we show that $rb(mathcal {T}_n, 5K_2)=2n+1$ for $n ge 11$.
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 colors. 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$.
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$.
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$. Upon 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.
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 each $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 matchings in graphs, made by Aharoni and Berger and others.