Can I read Short Rainbow Cycles in Graphs and Matroids on EtoBox?

Short Rainbow Cycles in Graphs and Matroids by DeVos, Matt; Drescher, Matthew; Funk, Daryl; de la Maza, Sebastián González Hermosillo; Guo, Krystal; Huynh, Tony; Mohar, Bojan; Montejano, Amanda is a scholarly article available to read on EtoBox.

What is Short Rainbow Cycles in Graphs and Matroids about?

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 \frac{n}{2} \rceil$, which is best possible. Our result settles a special case of a strengthening of the Caccetta-H\"aggkvist 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.

Author

DeVos, Matt; Drescher, Matthew; Funk, Daryl; de la Maza, Sebastián González Hermosillo; Guo, Krystal; Huynh, Tony; Mohar, Bojan; Montejano, Amanda

Published

2018

Language

EN