اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدExact rainbow numbers for matchings in plane triangulations
140
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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$.
قيم البحث
اقرأ أيضاً
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 col
ors. 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$.
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 know
n 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$.
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.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
