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

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

Received 8 October 2019

Accepted 9 October 2020

Published 31 January 2022