On a rainbow version of Dirac's theorem

2020/05/19 by Felix Joos, Jaehoon Kim · 9 citations
Mathematics · #Algebraic and Geometric Analysis #Mathematics and Applications #Advanced Operator Algebra Research

paper · doi:10.1112/blms.12343

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.

Cited by

• A general approach to transversal versions of Dirac‐type theorems
• Universality for transversal Hamilton cycles
• Rainbow Pancyclicity in Graph Systems
• Transversal Hamilton Paths and Cycles
• Ore's Theorem for rainbow Hamiltonian-connected graphs
• Rainbow Perfect Matchings for 4-Uniform Hypergraphs
• Transversal Hamilton Cycle in Hypergraph Systems
• Universality for transversal powers of Hamilton cycles
• Rainbow structures in a collection of graphs with degree conditions
• Unbounded degree spanning hypertrees in Dirac hypergraphs

Related

• A general approach to transversal versions of dirac-type theorems
• A general approach to transversal versions of Dirac-type theorems
• A general approach to transversal versions of Dirac‐type theorems
• From one to many rainbow Hamiltonian cycles
• Transversal Hamilton cycles in digraph collections