Loading...
Loading...

Go to the content (press return)

Rainbow perfect matchings in r-partite graph structures

Author
Cano, M.; Perarnau, G.; Serra, O.
Type of activity
Journal article
Journal
Electronic notes in discrete mathematics
Date of publication
2016-10-03
Volume
54
First page
193
Last page
198
DOI
https://doi.org/10.1016/j.endm.2016.09.034 Open in new window
Project funding
MTM2014-54754-P
Repository
http://hdl.handle.net/2117/101772 Open in new window
URL
http://www.sciencedirect.com/science/article/pii/S1571065316301287 Open in new window
Abstract
A matching M in an edge–colored (hyper)graph is rainbow if each pair of edges in M have distinct colors. We extend the result of Erdos and Spencer on the existence of rainbow perfect matchings in the complete bipartite graph Kn,n to complete bipartite multigraphs, dense regular bipartite graphs and complete r-partite r-uniform hypergraphs. The proof of the results use the Lopsided version of the Local Lovász Lemma.
Citation
Cano, M., Perarnau, G., Serra, O. Rainbow perfect matchings in r-partite graph structures. "Electronic notes in discrete mathematics", 3 Octubre 2016, vol. 54, p. 193-198.
Keywords
Lovász Local lemma, Rainbow matchings
Group of research
CGA -Computational Geometry and Applications
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

Attachments