Short rainbow cycles in graphs and matroids

Authors
  • M. DeVos
  • M. Drescher
  • D. Funk
  • S.G. Hermosillo de la Maza
  • K. Guo ORCID logo
  • T. Huynh
  • B. Mohar
  • A. Montejano
Publication date 02-2021
Journal Journal of Graph Theory
Volume | Issue number 96 | 2
Pages (from-to) 192-202
Organisations
  • Faculty of Science (FNWI) - Korteweg-de Vries Institute for Mathematics (KdVI)
Abstract Let G be a simple n-vertex graph and c be a coloring of E(G)with n colors, where each color class has size at least 2. We prove that (G,c) contains a rainbow cycle of length at most ⌈n-2⌉, 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.
Document type Article
Language English
Published at https://doi.org/10.1002/jgt.22607
Other links https://www.scopus.com/pages/publications/85087152639
Permalink to this page
Back