Rainbow Perfect Matchings in Complete Bipartite Graphs: Existence and Counting

DOI10.1017/S096354831300028XzbMath1282.05190arXiv1104.2132MaRDI QIDQ5397732

Guillem Perarnau, Oriol Serra

Publication date: 24 February 2014

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1104.2132

zbMATH Keywords

asymptotic enumerationLatin transversal

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Orthogonal arrays, Latin squares, Room squares (05B15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Asymptotic enumeration (05A16) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (7)

Bounded colorings of multipartite graphs and hypergraphs ⋮ Rainbow tetrahedra in Cayley graphs ⋮ Nordhaus-Gaddum for treewidth ⋮ Rainbow perfect matchings in \(r\)-partite graph structures ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Rainbow matchings and Hamilton cycles in random graphs ⋮ From one to many rainbow Hamiltonian cycles

Cites Work

• A proof of Snevily's conjecture.
• Lopsided Lovász Local lemma and Latin transversals
• The number of transversals in a Latin square
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• Transversals of latin squares and their generalizations
• Rainbow Hamilton cycles in random regular graphs
• The cycle structure of two rows in a random Latin square
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• A lower bound for the length of a partial transversal in a Latin square
• Unnamed Item

This page was built for publication: Rainbow Perfect Matchings in Complete Bipartite Graphs: Existence and Counting