اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLarge rainbow matchings in edge-colored graphs with given average color degree
101
0
0.0
(
0
)
تأليف
Wenling Zhou
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 existence of rainbow matchings in edge-colored graph G with average color degree at least 2k, and proved some sufficient conditions for a rainbow marching of size k in G. The sufficient conditions include that |V(G)|>=12k^2+4k, or G is a properly edge-colored graph with |V(G)|>=8k. In this paper, we show that every edge-colored graph G with |V(G)|>=4k-4 and average color degree at least 2k-1 contains a rainbow matching of size k. In addition, we also prove that every strongly edge-colored graph G with average degree at least 2k-1 contains a rainbow matching of size at least k. The bound is sharp for complete graphs.
قيم البحث
اقرأ أيضاً
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 $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
g literature on rainbow triangles in edge-colored complete graphs. Fujita and Magnant showed that for an edge-colored complete graph $G$ of order $n$, if $delta^c(G)geq frac{n+1}{2}$, then every vertex of $G$ is contained in a rainbow triangle. In this paper, we show that if $delta^c(G)geq frac{n+k}{2}$, then every vertex of $G$ is contained in at least $k$ rainbow triangles, which can be seen as a generalization of their result. Li showed that for an edge-colored graph $G$ of order $n$, if $delta^c(G)geq frac{n+1}{2}$, then $G$ contains a rainbow triangle. We show that if $G$ is complete and $delta^c(G)geq frac{n}{2}$, then $G$ contains a rainbow triangle and the bound is sharp. Hu et al. showed that for an edge-colored graph $G$ of order $ngeq 20$, if $delta^c(G)geq frac{n+2}{2}$, then $G$ contains two vertex-disjoint rainbow triangles. We show that if $G$ is complete with order $ngeq 8$ and $delta^c(G)geq frac{n+1}{2}$, then $G$ contains two vertex-disjoint rainbow triangles. Moreover, we improve the result of Hu et al. from $ngeq 20$ to $ngeq 7$, the best possible.
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
bow $ell$-cycle $C_{ell}$ whenever $n ge 432 ell$. This result is sharp for all odd integers $ell geq 3$, and extends earlier work of the authors for when $ell$ is even.
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
w cycles of edge-colored graphs. In this paper, we show that (i) if $delta^c(G)>frac{3n-3}{4}$, then every vertex of $G$ is contained in a rainbow triangle; (ii) $delta^c(G)>frac{3n}{4}$, then every vertex of $G$ is contained in a rainbow $C_4$; and (iii) if $G$ is complete, $ngeq 8k-18$ and $delta^c(G)>frac{n-1}{2}+k$, then $G$ contains a rainbow cycle of length at least $k$. Some gaps in previous publications are also found and corrected.
Let $G$ be a simple graph with maximum degree $Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>Delta(G)lfloor |V(H)|/2 rfloor$. Chetwynd and Hilton in 1985 conjectured that a graph $G$ with $Delta(G)>|V(G)|/3$ has chromatic index $Delta(G)$ i
f and only if $G$ contains no overfull subgraph. The 1-factorization conjecture is a special case of this overfull conjecture, which states that for even $n$, every regular $n$-vertex graph with degree at least about $n/2$ has a 1-factorization and was confirmed for large graphs in 2014. Supporting the overfull conjecture as well as generalizing the 1-factorization conjecture in an asymptotic way, in this paper, we show that for any given $0<varepsilon <1$, there exists a positive integer $n_0$ such that the following statement holds: if $G$ is a graph on $2nge n_0$ vertices with minimum degree at least $(1+varepsilon)n$, then $G$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
