2018/06/03 by Matt DeVos, DeVos, Matt, Matthew Drescher +13 · 1 citation
#math.CO #cs.DM
paper · pdf · doi:10.48550/arxiv.1806.00825
Let G be a simple n-vertex graph and c be a colouring of E(G) with n colours, where each colour class has size at least 2. We prove that (G,c) contains a rainbow cycle of length at most \lceil (n)/(2) \rceil, which is best possible. Our result settles a special case of a strengthening of the Caccetta-Häggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids.