OpenAlex ·
Edge and spectral conditions for rainbow pancyclicity in graph collections
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.23532
- Original
- Read it at the publisher
- Topics
Abstract
Let $\mathbf{G}=\{G_1,\dots,G_{n}\}$ be a collection of not necessarily distinct $n$-vertex graphs with a common vertex set $V$. A cycle $C$ with $V(C)\subseteq V$ and $|E(C)|\leq n$ is called \emph{rainbow} in $\mathbf{G}$, if there exists an injection $ϕ\colon E(C)\to [n]$ such that $e\in E(G_{ϕ(e)})$ for each $e\in E(C)$. The graph collection $\mathbf{G}$ is said to be \emph{rainbow pancyclic} if it contains a rainbow cycle of every length from 3 to $n$. In this paper, we show that if $e(G_i)\ge \binom{n-1}{2}+1$ for each $i\in[n]$ with $n\ge 3$, then $\mathbf{G}$ is rainbow pancyclic, apart from three explicitly described exceptional graph collections. This answers Problem $1$ of [Discrete Math., \textbf {348}(2025), 114600] and strengthens the result from rainbow Hamiltonicity to rainbow pancyclicity. As a consequence, we obtain that if $ρ(G_i)>n-2$ for each $i\in[n]$, then $\mathbf{G}$ is rainbow pancyclic unless $G_1=G_2=\dots=G_n\cong K_1\vee(K_{n-2}\cup K_1)$, which improves Theorem $5$ of [Discrete Math., \textbf {348}(2025), 114600]. We also characterize all graph collections that are not rainbow pancyclic under the condition $ρ(G_i)\ge n-2$ for each $i\in[n]$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Vector Balancing in Polynomial Time
Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
A general counting and sampling Lovász local lemma
Dual-GNN Multilevel Coarsening for Maximum Independent Set
Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.