Rainbow Even Cycles
Zichao Dong, Zijian Xu · SIAM Journal on Discrete Mathematics · 2024
Abstract. We prove that every family of (not necessarily distinct) even cycles [Formula: see text] on some fixed [Formula: see text]-vertex set has a rainbow even cycle (that is, a set of edges from distinct [Formula: see text]’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 [Formula: see text].