Rainbow pancyclicity in graph systems (Q2048556): Difference between revisions

Summary: Let \(G_1,\ldots,G_n\) be graphs on the same vertex set of size \(n\), each graph with minimum degree \(\delta(G_i)\geqslant n/2\). A recent conjecture of Aharoni asserts that there exists a rainbow Hamiltonian cycle i.e. a cycle with edge set \(\{e_1,\ldots,e_n\}\) such that \(e_i\in E(G_i)\) for \(1\leqslant i \leqslant n\). This can be viewed as a rainbow version of the well-known Dirac theorem. In this paper, we prove this conjecture asymptotically by showing that for every \(\varepsilon>0\), there exists an integer \(N>0\), such that when \(n>N\) for any graphs \(G_1,\ldots,G_n\) on the same vertex set of size \(n\) with \(\delta(G_i)\geqslant (\frac{1}{2}+\varepsilon)n\), there exists a rainbow Hamiltonian cycle. Our main tool is the absorption technique. Additionally, we prove that with \(\delta(G_i)\geqslant \frac{n+1}{2}\) for each \(i\), one can find rainbow cycles of length \(3,\ldots,n-1\).