On a rainbow version of Dirac's theorem

By Felix Joos, Jaehoon Kim. Bulletin of the London Mathematical Society, 2019

66 citations recorded by the source corpus.

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.

Subfields: Applied Mathematics, Geometry and Topology, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/588d8499d1010c3615c4c0b4848560154fdff615