Contents Online

# Journal of Combinatorics

## Volume 12 (2021)

### Number 4

### On even rainbow or nontriangular directed cycles

Pages: 589 – 662

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

#### Authors

#### 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.

Received 8 October 2019

Accepted 9 October 2020

Published 31 January 2022