Dirac-type Problem of Rainbow matchings and Hamilton cycles in Random Graphs

2022/11/10 by Asaf Ferber, Jie Han, Ferber, Asaf +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2211.05477

openalex publication_date 2022/11/10 · openalex created_date 2022/11/16 · openalex updated_date 2026/07/28

Abstract

Given a family of graphs G₁,…,G_n on the same vertex set [n], a rainbow Hamilton cycle is a Hamilton cycle on [n] such that each G_c contributes exactly one edge. We prove that if G₁,…,G_n are independent samples of G(n,p) on the same vertex set [n], then for each ε>0, whp, every collection of spanning subgraphs H_c⊆ G_c, with δ(H_c)≥((1)/(2)+ε)np, admits a rainbow Hamilton cycle. A similar result is proved for rainbow perfect matchings in a family of n/2 graphs on the same vertex set [n].

Cited by

• Clique factors in random samplings of regular graphs
• Transversal packings in families of percolated hypergraphs

Related

• Rainbow perfect matchings and Hamilton cycles in the random geometric\n graph
• Rainbow Pancyclicity in Graph Systems
• Rainbow Matchings and Hamilton Cycles in Random Graphs
• Rainbow Hamilton cycles in random regular graphs
• A Rainbow Dirac's Theorem