Pancyclicity in Graph Families with the Ore-Type Condition

Abstract

Let $n\in \mathbb{N}$ with $n\ge 3$, and let $\mathcal{G}=\{G_i:i\in [n]\}$ be a family of $n$-vertex graphs on a common vertex set $V$, where the graphs in the family do not need to be distinct. A graph $H$ with vertex set $V$ is \emph{rainbow} in $\mathcal{G}$ if there exists an injection $\ddot{I}•:E(H)\to [n]$ such that $e\in E(G_{\ddot{I}•(e)})$ for every edge $e\in E(H)$, where $|E(H)|\le n$. In 2020, Joos and Kim proved that $\mathcal{G}$ contains a rainbow Hamiltonian cycle under the Dirac-type condition. Recently, Liu, Chen, and Ma generalized this result by replacing the Dirac-type condition with a more general Ore-type condition involving degree sums of non-adjacent vertices: If $\ddot{I}ƒ(\mathcal{G})\ge n$, then $\mathcal{G}$ contains a rainbow Hamiltonian cycle, where the Ore-type condition $\ddot{I}ƒ(\mathcal{G})$ is defined as follows: $\ddot{I}ƒ(\mathcal{G})=\min \{d_p(u)+d_q(v)\mid uv\notin E(G_i)\text{ for some }i\in [n]\text{ and for all }p,q\in [n]\}.$ In this paper, under the Ore-type condition, we show that either each vertex of $V$ is contained in a rainbow cycle of length $\ell$ for every $\ell \in [4,n]$, or $G_1=\cdots =G_n=K_{\frac{n}{2},\frac{n}{2}}$. As a corollary, we deduce the rainbow pancyclicity of $\mathcal{G}$, which supports the famous meta-conjecture posed by Bondy. Furthermore, we prove rainbow vertex-pancyclicity of $\mathcal{G}$ under the Ore-type condition and provide an extremal graph family to show that the result is sharp.

18 pages, 4 figures