Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Rainbow perfect matchings in complete bipartite graphs: existence and counting

Autor
Perarnau-Llobet, G.; Serra, O.
Tipus d'activitat
Article en revista
Revista
Combinatorics probability and computing
Data de publicació
2013-09
Volum
22
Número
5
Pàgina inicial
783
Pàgina final
799
DOI
https://doi.org/10.1017/S096354831300028X Obrir en finestra nova
Resum
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...
Paraules clau
Combinatorics Probability and Computing
Grup de recerca
COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants