On even rainbow or nontriangular directed cycles

DOI10.4310/JOC.2021.V12.N4.A4MaRDI QIDQ2073645zbMATH OpenOpenAlexFDO

Authors Andrzej Czygrinow, Theodore Molla, B. Nagle, Roy Oursler

Publication date 3 February 2022

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.02049

zbMATH Keywords

directed graphsedge-coloredrainbow subgraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: Let $G=(V,E)$ be an $n$-vertex edge-colored graph. In 2013, H. Li proved that if every vertex $vinV$ 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 $vinV$ is incident to at least $(n+5)/3$ distinctly colored edges, where $ngeq{n}_0(ell)$ is sufficiently large, then $G$ admits an even rainbow $ell$-cycle $C_{ell}$. This result is best possible whenever $ellotequiv0$ (mod 3). Correspondingly, we also show that for a fixed (even or odd) integer $ellgeq4$, every large $n$-vertex oriented graph $vecG=(V,vecE)$ 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, K"uhn, and Osthus, who proved a similar statement for oriented graphs with large semi-degree. Our proofs are based on the stability method.

Recommendations

• On odd rainbow cycles in edge-colored graphs
• Note on rainbow cycles in edge-colored graphs
• Rainbow triangles and the Caccetta-Häggkvist conjecture
• Rainbow cycles in edge-colored graphs
• Rainbow Turán problem for even cycles

Cited in

(3)

• Rainbow Turán problem for even cycles
• On odd rainbow cycles in edge-colored graphs
• Rainbow even cycles

This page was built for publication: On even rainbow or nontriangular directed cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2073645)