Do you want to publish a course? Click here

On Even Rainbow or Nontriangular Directed Cycles

170   0   0.0 ( 0 )
 Added by Theodore Molla
 Publication date 2019
  fields
and research's language is English




Ask ChatGPT about the research

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.



rate research

Read More

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.
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$ 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.
For a finite subset $A$ of $mathbb{Z}_{>0}$, Lazar and Wachs (2019) conjectured that the number of cycles on $A$ with only even-odd drops is equal to the number of D-cycles on $A$. In this note, we introduce cycles on a multiset with only even-odd drops and prove bijectively a multiset version of their conjecture. As a consequence, the number of cycles on $[2n]$ with only even-odd drops equals the Genocchi number $g_n$. With Laguerre histories as an intermediate structure, we also construct a bijection between a class of permutations of length $2n-1$ known to be counted by $g_n$ invented by Dumont and the cycles on $[2n]$ with only even-odd drops.
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.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا