Rainbow even cycles

Abstract

We prove that every family of (not necessarily distinct) even cycles $D_1,\dots ,D_{\lfloor 1.2(n-1)\rfloor +1}$ on some fixed $n$-vertex set has a rainbow even cycle (that is, a set of edges from distinct $D_i$'s, forming an even cycle). This resolves an open problem of Aharoni, Briggs, Holzman and Jiang. Moreover, the result is best possible for every positive integer $n$.

20 pages, 10 figures

References in corpus (2)

• On a rainbow version of Dirac's theorem
• Rainbow odd cycles