# Journal of Combinatorics

## Volume 12 (2021)

### On even rainbow or nontriangular directed cycles

Pages: 589 – 662

DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n4.a4

#### Authors

Andrzej Czygrinow (School of Mathematical and Statistical Sciences, Arizona State University, Tempe, Az., U.S.A.)

Theodore Molla (Department of Mathematics and Statistics, University of South Florida, Tampa, Fl., U.S.A.)

Brendan Nagle (Department of Mathematics and Statistics, University of South Florida, Tampa, Fl., U.S.A.)

Roy Oursler (School of Mathematical and Statistical Sciences, Arizona State University, Tempe, Az., U.S.A.)

#### Abstract

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 \not \equiv 0 (\operatorname{mod} 3)$. Correspondingly, we also show that for a fixed (even or odd) integer $\ell \geq 4$, every large $n$-vertex oriented graph $\overrightarrow{G}=(V,\overrightarrow{E})$ with minimum outdegree at least $(n+1)/3$ admits a (consistently) directed $\ell$-cycle $\overrightarrow{C}_\ell$. Our latter result relates to one of Kelly, Kühn, and Osthus, who proved a similar statement for oriented graphs with large semi-degree. Our proofs are based on the stability method.

#### Keywords

edge-colored, rainbow subgraph, directed graphs

#### 2010 Mathematics Subject Classification

05C20, 05C35, 05C38

The first-named author was partially supported by Simons Foundation Grant #521777.

The second-named author was partially supported by NSF Grants DMS 1500121 and DMS 1800761.

The third-named author was partially supported by NSF Grant DMS 1700280.