On a rainbow version of Dirac's theorem

Abstract

For a collection G={G1,MIDLINE HORIZONTAL ELLIPSIS,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 phi:E(H)->[s] such that e is an element of E(G phi(e)) for all e is an element of E(H). We prove that for |V|=s > 3 and delta(Gi)> s/2 for each i is an element of[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.