Full rainbow matchings in graphs and hypergraphs

Let G be a simple graph that is properly edge-coloured with m colours and let \[\mathcal{M} = \{ {M_1},...,{M_m}\} \] be the set of m matchings induced by the colours in G . Suppose that \[m \leqslant n - {n^c}\] , where \[c > 9/10\] , and every matching in \[\mathcal{M}\] has size n . Then G con...

Full description

Saved in:
Bibliographic Details
Published in:Combinatorics, probability & computing probability & computing, 2021-09, Vol.30 (5), p.762-780
Main Authors: Gao, Pu, Ramadurai, Reshma, Wanless, Ian M., Wormald, Nick
Format: Article
Language:English
Subjects:
Combinatorics
Graph coloring
Graph theory
Graphs
Matching
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G be a simple graph that is properly edge-coloured with m colours and let \[\mathcal{M} = \{ {M_1},...,{M_m}\} \] be the set of m matchings induced by the colours in G . Suppose that \[m \leqslant n - {n^c}\] , where \[c > 9/10\] , and every matching in \[\mathcal{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 \leqslant i \leqslant m\] . This answers an open problem of Pokrovskiy and gives an affirmative answer to a generalization 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.
ISSN:0963-5483
1469-2163
DOI:10.1017/S0963548320000620