Full rainbow matchings in graphs and hypergraphs

Abstract

Let $G$ be a simple graph that is properly edge coloured with $m$ colours and let $\M=\{M_1,\ldots, M_m\}$ be the set of $m$ matchings induced by the colours in $G$. Suppose that $m\le n-n^c$, where $c>9/10$, and every matching in $\M$ has size $n$. Then $G$ contains a full rainbow matching, i.e.\ a matching that contains exactly one edge from $M_i$ for each $1\le i\le m$. This answers an open problem of Pokrovskiy and gives an affirmative answer to a generalisation of a special case of a conjecture of Aharoni and Berger. Related results are also found for multigraphs with edges of bounded multiplicity, and for hypergraphs. Finally, we provide counterexamples to several conjectures on full rainbow matchings made by Aharoni and Berger.

This updated version combines another arxiv document:1710.04807

References in corpus (2)

• Decompositions into spanning rainbow structures
• On the number of symbols that forces a transversal

Cited by in corpus (1)

• Bounded degree graphs and hypergraphs with no full rainbow matchings