Rainbow matchings in properly colored multigraphs

Journal article

Aharoni and Berger conjectured that in any bipartite multigraph that is properly edge-colored by $n$ colors with at least $n + 1$ edges of each color there must be a matching that uses each color exactly once. In this paper we consider the same question without the bipartiteness assumption. We show that in any multigraph with edge multiplicities $o(n)$ that is properly edge-colored by $n$ colors with at least $n + o(n)$ edges of each color there must be a matching of size $n-O(1)$ that uses each color at most once. Read More: https://epubs.siam.org/doi/abs/10.1137/17M1151742

Authors: Keevash, P; Yepremyan, L

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Journal: SIAM Journal on Discrete Mathematics
• Volume: 32
• Issue: 3
• Pages: 1577–1584
• Publication date: 2018-07-10
• Acceptance date: 2018-05-23
• DOI: 10.1137/17M1151742
• EISSN: 1095-7146
• ISSN: 0895-4801
• Keywords: FFR; latin squares; matchings; graph theory