Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRainbow odd cycles
103
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove that every family of (not necessarily distinct) odd cycles $O_1, dots, O_{2lceil n/2 rceil-1}$ in the complete graph $K_n$ on $n$ vertices has a rainbow odd cycle (that is, a set of edges from distinct $O_i$s, forming an odd cycle). As part of the proof, we characterize those families of $n$ odd cycles in $K_{n+1}$ that do not have any rainbow odd cycle. We also characterize those families of $n$ cycles in $K_{n+1}$, as well as those of $n$ edge-disjoint nonempty subgraphs of $K_{n+1}$, without any rainbow cycle.
rate research
Read More
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.
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 establish a corresponding result for fixed even rainbow $ell$-cycles $C_{ell}$: if every vertex $v in V$ is incident to at least $(n+5)/3$ distinctly colored edges, where $n geq n_0(ell)$ is sufficiently large, then $G$ admits an even rainbow $ell$-cycle $C_{ell}$. This result is best possible whenever $ell otequiv 0$ (mod 3). Correspondingly, we also show that for a fixed (even or odd) integer $ell geq 4$, every large $n$-vertex oriented graph $vec{G} = (V, vec{E})$ with minimum outdegree at least $(n+1)/3$ admits a (consistently) directed $ell$-cycle $vec{C}_{ell}$. Our latter result relates to one of Kelly, Kuhn, and Osthus, who proved a similar statement for oriented graphs with large semi-degree. Our proofs are based on the stability method.
Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $2$. We prove that $(G,c)$ contains a rainbow cycle of length at most $lceil frac{n}{2} rceil$, which is best possible. Our result settles a special case of a strengthening of the Caccetta-Haggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids.
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 rainbow 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.
The Ramsey number $r(H)$ of a graph $H$ is the minimum $n$ such that any two-coloring of the edges of the complete graph $K_n$ contains a monochromatic copy of $H$. The threshold Ramsey multiplicity $m(H)$ is then the minimum number of monochromatic copies of $H$ taken over all two-edge-colorings of $K_{r(H)}$. The study of this concept was first proposed by Harary and Prins almost fifty years ago. In a companion paper, the authors have shown that there is a positive constant $c$ such that the threshold Ramsey multiplicity for a path or even cycle with $k$ vertices is at least $(ck)^k$, which is tight up to the value of $c$. Here, using different methods, we show that the same result also holds for odd cycles with $k$ vertices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
