Rainbow matchings in properly-coloured multigraphs

Author: 

Keevash, P
Yepremyan, L

Publication Date: 

10 July 2018

Journal: 

SIAM Journal on Discrete Mathematics

Last Updated: 

2020-05-09T23:40:46.817+01:00

Issue: 

3

Volume: 

32

DOI: 

10.1137/17M1151742

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: 

Submitted

Publication Type: 

Journal Article