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.
Original language | English (US) |
---|---|
Journal | SIAM Journal on Discrete Mathematics |
Volume | 35 |
Issue number | 4 |
DOIs | |
State | Published - 2021 |
Keywords
- Cactus graph
- Odd cycle
- Rado's theorem for matroids
- Rainbow cycle
ASJC Scopus subject areas
- General Mathematics