On a rainbow version of Dirac's theorem

Abstract

For a collection $\mathbf{G}=\{G_1,\dots ,G_s\}$ of not necessarily distinct graphs on the same vertex set $V$, a graph $H$ with vertices in $V$ is a $\mathbf{G}$-transversal if there exists a bijection $\varphi :E(H)\to [s]$ such that $e\in E(G_{\varphi (e)})$ for all $e\in E(H)$. We prove that for $|V|=s\ge 3$ and $\delta (G_i)\ge s/2$ for each $i\in [s]$, there exists a $\mathbf{G}$-transversal that is a Hamilton cycle. This confirms a conjecture of Aharoni. We also prove an analogous result for perfect matchings.

References in corpus (1)

• Rainbow Pancyclicity in Graph Systems

Cited by in corpus (9)

• On a rainbow extremal problem for color-critical graphs
• Rainbow Pancyclicity in Graph Systems
• Rainbow spanning structures in graph and hypergraph systems
• Rainbow even cycles
• On the multicolor Turán conjecture for color-critical graphs
• Co-degree threshold for rainbow perfect matchings in uniform hypergraphs
• Transversal Hamilton cycle in hypergraph systems
• The absence of monochromatic triangle implies various properly colored spanning trees
• Transversal Hamilton cycles in digraph collections