Loading...
Loading...

Go to the content (press return)

Rainbow perfect matchings in complete bipartite graphs: existence and counting

Author
Perarnau-Llobet, G.; Serra, O.
Type of activity
Journal article
Journal
Combinatorics probability and computing
Date of publication
2013-09
Volume
22
Number
5
First page
783
Last page
799
DOI
https://doi.org/10.1017/S096354831300028X Open in new window
Abstract
A perfect matching M in an edge-coloured complete bipartite graph Kn,n is rainbow if no pair of edges in M have the same colour. We obtain asymptotic enumeration results for the number of rainbow perfect matchings in terms of the maximum number of occurrences of each colour. We also consider two natural models of random edge-colourings of Kn,n and show that if the number of colours is at least n, then there is with high probability a rainbow perfect matching. This in particular shows that almost...
Keywords
Combinatorics Probability and Computing
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants