RAINBOW MATCHINGS IN PROPERLY COLORED MULTIGRAPHS

Author: 

Keevash, P
Yepremyan, L

Publication Date: 

2018

Journal: 

SIAM JOURNAL ON DISCRETE MATHEMATICS

Last Updated: 

2019-06-19T00:30:57.503+01:00

Issue: 

3

Volume: 

32

DOI: 

10.1137/17M1151742

page: 

1577-1584

abstract: 

© 2018 Society for Industrial and Applied Mathematics. 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.

Symplectic id: 

735439

Download URL: 

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article