Full rainbow matchings in graphs and hypergraphs

Pu Gao; Reshma Ramadurai; Ian M. Wanless; Nick Wormald

doi:10.1017/S0963548320000620

Full rainbow matchings in graphs and hypergraphs

Pu Gao, Reshma Ramadurai, Ian M. Wanless, Nick Wormald

School of Mathematics

Research output: Contribution to journal › Article › Research › peer-review

6 Citations (Scopus)

Abstract

Let G be a simple graph that is properly edge-coloured with m colours and let be the set of m matchings induced by the colours in G. Suppose that, where 9/10\]]]>, and every matching in has size n. Then G contains a full rainbow matching, i.e. a matching that contains exactly one edge from Mi for each. 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.

Original language	English
Pages (from-to)	762-780
Number of pages	19
Journal	Combinatorics, Probability and Computing
Volume	30
Issue number	5
DOIs	https://doi.org/10.1017/S0963548320000620
Publication status	Published - Sept 2021

Keywords

05C70
05D15
2020 MSC Codes:

Access to Document

10.1017/S0963548320000620Licence: Unspecified

Cite this

@article{52de0f229a8d40d6a173a2bfbc133282,

title = "Full rainbow matchings in graphs and hypergraphs",

abstract = "Let G be a simple graph that is properly edge-coloured with m colours and let be the set of m matchings induced by the colours in G. Suppose that, where 9/10\]]]>, and every matching in has size n. Then G contains a full rainbow matching, i.e. a matching that contains exactly one edge from Mi for each. 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.",

keywords = "05C70, 05D15, 2020 MSC Codes:",

author = "Pu Gao and Reshma Ramadurai and Wanless, {Ian M.} and Nick Wormald",

year = "2021",

month = sep,

doi = "10.1017/S0963548320000620",

language = "English",

volume = "30",

pages = "762--780",

journal = "Combinatorics, Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "5",

}

TY - JOUR

T1 - Full rainbow matchings in graphs and hypergraphs

AU - Gao, Pu

AU - Ramadurai, Reshma

AU - Wanless, Ian M.

AU - Wormald, Nick

PY - 2021/9

Y1 - 2021/9

N2 - Let G be a simple graph that is properly edge-coloured with m colours and let be the set of m matchings induced by the colours in G. Suppose that, where 9/10\]]]>, and every matching in has size n. Then G contains a full rainbow matching, i.e. a matching that contains exactly one edge from Mi for each. 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.

AB - Let G be a simple graph that is properly edge-coloured with m colours and let be the set of m matchings induced by the colours in G. Suppose that, where 9/10\]]]>, and every matching in has size n. Then G contains a full rainbow matching, i.e. a matching that contains exactly one edge from Mi for each. 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.

KW - 05C70

KW - 05D15

KW - 2020 MSC Codes:

UR - http://www.scopus.com/inward/record.url?scp=85100007959&partnerID=8YFLogxK

U2 - 10.1017/S0963548320000620

DO - 10.1017/S0963548320000620

M3 - Article

AN - SCOPUS:85100007959

SN - 0963-5483

VL - 30

SP - 762

EP - 780

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 5

ER -

Full rainbow matchings in graphs and hypergraphs

Abstract

Keywords

Access to Document

Other files and links

Probabilistic combinatorics: Properties of large networks

Matchings in Combinatorial Structures

Advances in the analysis of random structures and their applications: relationships among models

Cite this

Full rainbow matchings in graphs and hypergraphs

Abstract

Keywords

Access to Document

Other files and links

Projects

Probabilistic combinatorics: Properties of large networks

Matchings in Combinatorial Structures

Advances in the analysis of random structures and their applications: relationships among models

Cite this