Journal title
SIAM Journal on Discrete Mathematics
DOI
10.1137/17M1151742
Issue
3
Volume
32
Last updated
2024-04-11T13:09:08.16+01:00
Page
1577-1584
Abstract
Aharoni and Berger conjectured that in any bipartite multigraph that is properly edge-coloured by $n$ colours with at least $n + 1$ edges of each colour there must be a matching that uses each colour 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-coloured by $n$ colours with at least $n + o(n)$ edges of each colour there must be a matching of size $n-O(1)$ that uses each colour at most once.
Symplectic ID
735439
Submitted to ORA
On
Favourite
Off
Publication type
Journal Article
Publication date
10 Jul 2018