@article{20567703e6e4467b8d69f861bbbc0856,
title = "Rainbow odd cycles",
abstract = "We prove that every family of (not necessarily distinct) odd cycles O1, . . ., O2[n/2] - 1 in the complete graph Kn on n vertices has a rainbow odd cycle (that is, a set of edges from distinct Oi's, forming an odd cycle). As part of the proof, we characterize those families of n odd cycles in Kn+1 that do not have any rainbow odd cycle. We also characterize those families of n cycles in Kn+1, as well as those of n edge-disjoint nonempty subgraphs of Kn+1, without any rainbow cycle.",
keywords = "Cactus graph, Odd cycle, Rado's theorem for matroids, Rainbow cycle",
author = "Ron Aharoni and Joseph Briggs and Ron Holzman and Zilin Jiang",
note = "Funding Information: \ast Received by the editors November 16, 2020; accepted for publication (in revised form) June 13, 2021; published electronically October 4, 2021. https://doi.org/10.1137/20M1380557 Funding: We acknowledge the financial support from the Ministry of Educational and Science of the Russian Federation in the framework of MegaGrant 075-15-2019-1926 when the first author worked on sections 2 and 3 of the paper. The first author was also supported in part by the United States-Israel Binational Science Foundation grant 2006099, the Israel Science Foundation grant 2023464, and the Discount Bank Chair at the Technion. This paper is part of a project that has received funding from the European Union's Horizon 2020 research and innovation program under the Marie Sk\lodowska-Curie grant agreement 823748. The third author's research was partly done during a visit at the Department of Mathematics, Princeton University, supported by the H2020-MSCA-RISE project CoSP-GA 823748. The work was done when the fourth author was an Applied Mathematics Instructor at Massachusetts Institute of Technology and was supported in part by an AMS-Simons Travel Grant and by US taxpayers through the NSF grant DMS-1953946. Publisher Copyright: {\textcopyright} 2021 Society for Industrial and Applied Mathematics",
year = "2021",
doi = "10.1137/20M1380557",
language = "English (US)",
volume = "35",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "4",
}