Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProperly colored and rainbow copies of graphs with few cherries
130
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let G be an n-vertex graph that contains linearly many cherries (i.e., paths on 3 vertices), and let c be a coloring of the edges of the complete graph K_n such that at each vertex every color appears only constantly many times. In 1979, Shearer conjectured that such a coloring c must contain a properly colored copy of G. We establish this conjecture in a strong form, showing that it holds even for graphs G with O(n^(4/3)) cherries and moreover this bound on the number of cherries is best possible up to a constant factor. We also prove that one can find a rainbow copy of such G in every edge-coloring of K_n in which all colors appear bounded number of times. Our proofs combine a framework of Lu and Szekely for using the lopsided Lovasz local lemma in the space of random bijections together with some additional ideas.
rate research
Read More
Properly colored cycles in edge-colored graphs are closely related to directed cycles in oriented graphs. As an analogy of the well-known Caccetta-H{a}ggkvist Conjecture, we study the existence of properly colored cycles of bounded length in an edge-colored graph. We first prove that for all integers $s$ and $t$ with $tgeq sgeq2$, every edge-colored graph $G$ with no properly colored $K_{s,t}$ contains a spanning subgraph $H$ which admits an orientation $D$ such that every directed cycle in $D$ is a properly colored cycle in $G$. Using this result, we show that for $rgeq4$, if the Caccetta-H{a}ggkvist Conjecture holds , then every edge-colored graph of order $n$ with minimum color degree at least $n/r+2sqrt{n}+1$ contains a properly colored cycle of length at most $r$. In addition, we also obtain an asymptotically tight total color degree condition which ensures a properly colored (or rainbow) $K_{s,t}$.
It is conjectured that every edge-colored complete graph $G$ on $n$ vertices satisfying $Delta^{mon}(G)leq n-3k+1$ contains $k$ vertex-disjoint properly edge-colored cycles. We confirm this conjecture for $k=2$, prove several additional weaker results for general $k$, and we establish structural properties of possible minimum counterexamples to the conjecture. We also reveal a close relationship between properly edge-colored cycles in edge-colored complete graphs and directed cycles in multi-partite tournaments. Using this relationship and our results on edge-colored complete graphs, we obtain several partial solutions to a conjecture on disjoint cycles in directed graphs due to Bermond and Thomassen.
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. 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 existing 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 rainbow $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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
