Let $G_1,\ldots,G_n$ be graphs on the same vertex set of size $n$, each graph with minimum degree $\delta(G_i)\ge 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\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 $\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)\ge (\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)\geq \frac{n+1}{2}$ for each $i$, one can find rainbow cycles of length $3,\ldots,n-1$.
@article{10_37236_9033,
author = {Yangyang Cheng and Guanghui Wang and Yi Zhao},
title = {Rainbow pancyclicity in graph systems},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {3},
doi = {10.37236/9033},
zbl = {1470.05088},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9033/}
}
TY - JOUR
AU - Yangyang Cheng
AU - Guanghui Wang
AU - Yi Zhao
TI - Rainbow pancyclicity in graph systems
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/9033/
DO - 10.37236/9033
ID - 10_37236_9033
ER -
%0 Journal Article
%A Yangyang Cheng
%A Guanghui Wang
%A Yi Zhao
%T Rainbow pancyclicity in graph systems
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9033/
%R 10.37236/9033
%F 10_37236_9033
Yangyang Cheng; Guanghui Wang; Yi Zhao. Rainbow pancyclicity in graph systems. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/9033
