Rainbow Pancyclicity in Graph Systems

Yangyang Cheng; Guanghui Wang; Yi Zhao

paper

Rainbow Pancyclicity in Graph Systems

arXiv:1909.11273

Abstract

Let $G_{1}, ..., G_{n}$ be graphs on the same vertex set of size $n$ , each graph with minimum degree $δ (G_{i}) \geq n /2$ . A recent conjecture of Aharoni asserts that there exists a rainbow Hamiltonian cycle i.e. a cycle with edge set ${e_{1}, ..., e_{n}}$ such that $e_{i} \in E (G_{i})$ for $1 \leq i \leq 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 $ε > 0$ , there exists an integer $N > 0$ , such that when $n > N$ for any graphs $G_{1}, ..., G_{n}$ on the same vertex set of size $n$ with $δ (G_{i}) \geq (\frac{1}{2} + ε) n$ , there exists a rainbow Hamiltonian cycle. Our main tool is the absorption technique. Additionally, we prove that with $δ (G_{i}) \geq \frac{n + 1}{2}$ for each $i$ , one can find rainbow cycles of length $3, ..., n - 1$ .