Abstract | ||
---|---|---|
We prove that every family of (not necessarily distinct) odd cycles O-1, . . . , O2[n/2]-1 in the complete graph K-n on n vertices has a rainbow odd cycle (that is, a set of edges from distinct O-i'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. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1137/20M1380557 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
rainbow cycle, odd cycle, cactus graph, Rado's theorem for matroids | Journal | 35 |
Issue | ISSN | Citations |
4 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
R. Aharoni | 1 | 47 | 25.92 |
Joseph Briggs | 2 | 0 | 1.35 |
Ron Holzman | 3 | 287 | 43.78 |
Zilin Jiang | 4 | 14 | 4.66 |