On a rainbow version of Dirac's theorem

For a collection G={G1,⋯,Gs} of not necessarily distinct graphs on the same vertex set V, a graph H with vertices in V is a G‐transversal if there exists a bijection ϕ:E(H)→[s] such that e∈E(Gϕ(e)) for all e∈E(H). We prove that for |V|=s⩾3 and δ(Gi)⩾s/2 for each i∈[s], there exists a G‐transversal t...

Full description

Saved in:
Bibliographic Details
Published in:The Bulletin of the London Mathematical Society 2020-06, Vol.52 (3), p.498-504
Main Authors: Joos, Felix, Kim, Jaehoon
Format: Article
Language:English
Subjects:
05C38
05C45
05C70 (primary)
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:For a collection G={G1,⋯,Gs} of not necessarily distinct graphs on the same vertex set V, a graph H with vertices in V is a G‐transversal if there exists a bijection ϕ:E(H)→[s] such that e∈E(Gϕ(e)) for all e∈E(H). We prove that for |V|=s⩾3 and δ(Gi)⩾s/2 for each i∈[s], there exists a G‐transversal that is a Hamilton cycle. This confirms a conjecture of Aharoni. We also prove an analogous result for perfect matchings.
ISSN:0024-6093
1469-2120
DOI:10.1112/blms.12343