On a rainbow version of Dirac's theorem

Abstract

For a collection G = { G 1 , ⋯ , G s } 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 δ ( G i ) ⩾ 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.

Topics & Concepts